Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ”ЛЬВІВСЬКА ПОЛІТЕХНІКА”
МОВИ ТА АВТОМАТИ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи №3-4
з дисципліни ”Формальні мови, граматики та автомати» ”
для студентів базового напряму ”Комп»ютерні науки ”
Затверджено
на засіданні кафедри
інформаційних систем та мереж
Протокол №1 від31.08.2012р.
Львів-2012
Мови та автомати: Методичні вказівки до лабораторної роботи №3-4 / Укл.:Захарія Л.М.. – Львів: Видавництво Національного університету ”Львівська політехніка”, 2007. – 19 с.
Укладачі Захарія Л.М., канд. фіз.-мат. наук, доц.
Відповідальний за випуск Пасічник В.В., доктор техн. наук., проф.
Рецензенти Верес О.М., канд.. техн. наук, доц.
Мета роботи: Необхідно розглянути основні властивості автоматів та принципи побудови мов. Показати зв’язок між граматиками і автоматами.
Запровадження ЕОМ у сферу інтелектуальної діяльності людини покликало до життя нову комунікативну систему «людина – машина – людина», в межах якої функціонування природної мови відрізняється від функціонування її в безпосередньому людському спілкуванні. Дослідження й опис природної мови в нових комунікативних системах вимагає й нових методів та підходів. Для розв’язування поставлених проблем прикладна лінгвістика повинна, використовуючи власне лінгвістичні дані, звертатися до багатьох інших дисциплін – кібернетики, математики, психології, фізики, медицини. Цим вона сприяє розширенню контактів мовознавчої науки з іншими науками і збагаченню лінгвістики новими точними методами дослідження мови.
Скінченний автомат без виходу – це п’ятірка , яка містить:
Скінченний автомат без виходу може бути заданий:
Приклад 4. Зобразити діаграму станів для автомата , де , , . Функція переходів задана таблицею 3. Діаграма станів зображена на рис. 4.
|
Табл. 3. |
||
|
Стан |
||
|
вхід |
||
|
0 |
1 |
|
Рис. 4.
Поняття функції переходів можна розширити і визначити її для всіх пар станів і ланцюжків. У такому разі, нехай – ланцюжок з . Тоді – стан, що обчислений з використанням послідовних символів з зліва направо, як вхідних символів, починаючи зі стану . Процес іде так: ; … Покладаємо . Ланцюжок сприймається, або розпізнається скінченним автоматом , якщо він переводить початковий стан у кінцевий стан – це означає, що стан є елементом множини .
Мова, що розпізнається, або сприймається автоматом , позначається через – це множина всіх ланцюжків, які розпізнаються автоматом . Два автомати називаються еквівалентними, якщо вони розпізнають одну і ту саму мову.
Приклад 5. Визначити мову, що розпізнається автоматом з діаграмою на рис. 8.
Рис. 5.
Відповідь: .
Приклад 6. Визначити мову, що розпізнається автоматом з діаграмою на рис. 6.
Рис. 6.
Відповідь: та є довільним ланцюжком.
Розглянуті скінченні автомати без виходу називаються детермінованими, оскільки для кожної пари стан – вхідний символ існує єдиний наступний стан, який задається функцією переходів. Існує інший тип автоматів без виходу – це недетерміновані автомати. У таких автоматах може бути декілька можливих наступних станів для кожної пари стан – вхідний символ.
Недетермінований скінченний автомат без виходу – це п’ятірка , де:
Приклад 7. На рис. 7 і у табл. 4 зображено діаграму і таблицю станів деякого недетермінованого автомата.
|
Табл. 2 |
||
|
Табличне задання недетермінованого автомата |
||
|
Стан |
||
|
вхід |
||
|
0 |
1 |
|
|
– |
||
|
– |
||
Рис. 7. Задання недетермінованого автомата множиною станів
Що означає, що недетермінований автомат розпізнає ланцюжок ?
Щоразу розглядається множина станів, яка визначається функцією . Автомат розпізнає, або сприймає ланцюжок , якщо є заключний стан у тій множині станів, яка отримана з початкового стану та ланцюжка . Мова розпізнається недетермінованим автоматом, якщо множина всіх ланцюжків (слів) цієї мови розпізнається цим автоматом.
Приклад 8. Знайти мову, що розпізнається автоматом з прикладу 7.
Неважко переконатись, що
.
Теорема 1. Якщо мова розпізнається недетермінованим скінченним автоматом , то існує також детермінований скінченний автомат , який розпізнає цю мову.
Теорема 2. Регулярна мова і тільки вона породжується регулярною граматикою.
Теорема 3. Для того, щоб мова була регулярною, необхідно і достатньо, щоб існував скіцнченнй автомат, який її розпізнає.
Проілюструємо кілька часткових випадків у розпізнаванні мов.
1. Множину допускає недетермінований автомат без заключних станів, зображений на рис. 8.
Рис.8.
2. Недетермінований автомат, який допускає має початковим і заключним станами (рис. 16).
Рис.9.
Тепер визначимо, як недетермінований скінченний автомат допускає ланцюжок . Перший вхідний символ переводить стан у множину , яка може містити більше одного стану. Наступний вхідний символ переводить кожний зі станів у деяку множину станів, і нехай буде об’єднанням цих множин. Ми продовжуємо цей процес, вибираючи на кожній стадії всі стани, отримані з використанням поточного вхідного символу і всіх станів, отриманих на попередній стадії. Недетермінований скінченний автомат допускає ланцюжок , якщо у множині станів, отриманій з початкового стану під дією ланцюжка , є заключний стан. Мова, яка допускається недетермінованим скінченним автоматом, – це множина всіх ланцюжків, які допускаються цим автоматом.
Приклад 9. Знайдемо мову, яка допускається недетермінованим скінченим автоматом з рис. 7.
Оскільки є заключним станом, і вхід 0 переводить у себе, то автомат допускає ланцюжки , 0, 00, 000, 0000, ... Стан також заключний, і нехай є у множині станів, що досягаються зі стану з ланцюжком на вході. Тоді ланцюжок допускається. Такими ланцюжками є та , де Оскільки інших заключних станів немає, то мова, яка допускається цим недетермінованим автоматом, є такою:
.
Важливо зазначити: якщо мова допускається недетермінованим автоматом, то вона також допускається детермінованим автоматом.
З теореми 1 випливає, що недетерміновані скінченні автомати допускають ті самі мови (множини ланцюжків), що і детерміновані скінченні автомати. Проте є причини розглядати недетерміновані автомати. Вони часто компактніші, і їх легше побудувати, ніж детерміновані. Крім того, хоча недетермінований автомат завжди можна перетворити у детермінований, детермінований може мати експоненціально більше станів. На щастя, такі випадки досить рідкісні.
Розв’язати завдання відповідно до свого порядкового номеру у списку групи. Завдання отримати у викладача. При оформленні лабораторної роботи дотримуватись вимог, які наведені в методичних вказівках. Оцінювання виконаної лабораторної роботи проводиться згідно кількості правильно розв’язаних завдань з відповідного варіанту. Завдання лабораторної роботи мають три рівня складності. Оцінювання виконання завдань першого рівня в п’ятибальній системі відповідає оцінці “задовільно”, другий рівень – “добре”, третій – “відмінно”.
Побудувати недетермінований скінчений автомат, що допускає мову, породжену даною граматикою; задати автомат діаграмою та таблицею. Для цього привести граматику до праволінійної граматики з правилами виводу А, або А і скористатись після цього наступною теоремою (:- позначають пусте слово).
Теорема . Кожна праволінійна мова являється автоматною.
Доведення. Можна припустити, що автоматна мова задається праволінійною граматикою, що не містить правила виду , де . Для побудови автомату, що буде розпізнавати ту ж мову покладемо Q = N, I = {S}, і .
Для цього використати наступну теорему
Теорема. Кожна автоматна мова є праволінійною.
Доведення.
Нехай мова розпізнається скінченним автоматом , де і I = {q0}. Побудуємо по такому скінченному автомату право лінійну граматику наступним чином N=Q, S=q0 і
|
1 |
14 |
||
|
2 |
15 |
||
|
3 |
16 |
||
|
4 |
17 |
||
|
5 |
18 |
||
|
6 |
19 |
||
|
7 |
20 |
||
|
8 |
21 |
||
|
9 |
22 |
||
|
10 |
23 |
||
|
11 |
24 |
||
|
12 |
25 |
||
|
13 |
26 |
Розглянемо ряд перетворень, які спрощують автоматні граматики ( і відповідні їм скінченні автомати)
Назвемо символ недосяжним в граматиці G = (N, T, P, S), якщо X не з»являється ні в одному виводі слова мови що породжується цією граматикою. Иншими словами, символ X являється недосяжним, якщо в G не існує виводу ні для яких .
Назвемо символ непродуктивним (бесплідним) в тій же граматиці, якщо в ній не існує виводу виду X =>* xwy, де w, x, y належить T*.
При уважному вивченні вищенаведених визначень стає зрозумілим, що
а) доцільно шукати не безпосередньо самі недосяжні символи, а послідовно визначати множину досяжних символів, починаючи з аксіоми; аналогічно множину продуктивних символів починаємо будувати, вибравши правила які не містять нетерміналів в правих частинах. Перетин множин досяжних і продуктивних не терміналів задає множину корисних не терміналів граматики ( автомату) - всі інші символи виявляються марними,
б) одночасне визначення досяжних і продуктивнихсимволів неможливо, так як відповідні процеси йдуть у протилежних напрямках (від кореня до листків і навпаки).
Алгоритм 1. Визначення досяжних нетерміналів граматики.
Вхід. Дано граматику G = (N, T, P, S).
Вихід. Граматика G' = (N', T', P', S) без недосяжних нетерміналів, така, що L(G') = L(G).
Метод. Виконати кроки 1-4:
(1) Покласти V0 = {S} і i = 1,
(2) Покласти Vi = {X | якщо в P є і ,
(3) Якщо , покласти i = i + 1 і перейти до кроку 2, в противному випадку перейти до кроку 4,
(4) Покласти . Включить в P' всі правила з P, які містять тільки символи з Vi.
Алгоритм 2. Визначення продуктивних символів граматики
Вхід. Граматика G = (N, T, P, S).
Вихід. Граматика G' = (N', T', P', S) без непродуктивних символів, така, що L(G') = L(G).
Метод. Виконати кроки 1-4:
(1) Покласти N' = T та i = 1,
(2) Покласти ,
(3) Якщо , покласти i = i + 1 і перейти до кроку 2, в противному випадку покласти Ne = Ni і перейти до кроку 4,
(4) Покласти , де P1 складається з правил множини P, що містять тільки символи з ,
Щоб видалити всі некорисні символи, необхідно застосувати до граматики спочатку Алгоритм 2, а потім Алгоритм 1.
Завдання.
1.Визначити множину корисних станів для представленого нижче автомату (корисних нетерміналів для відповідної цьому автомату граматики)
2. На основі свого варіанту з завдання 5.1 придумати автомат з недосяжними і непродуктивними станами. Звести отриманий автомат до автомату з одним вхідним і одним вихідним станом, який містив би тільки продуктивні стани.
|
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Кафедра інформаційних систем та мереж Лабораторна робота №3-4 на тему МОВИ ТА АВТОМАТИ Виконав (Виконала) студент (студентка) групи СА-99 Прізвище та ініціали студента Прийняв (Прийняла) Посада Прізвище та ініціали викладача Львів-200% |
НАВЧАЛЬНЕ ВИДАННЯ
МОВИ ТА АВТОМАТИ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи №3-4
з дисципліни ”Формальні мови та граматики ”
для студентів спеціальності ”Системний аналіз”
Укладачі Захарія Л.М.
Редактор
Комп’ютерне верстання