Малюнок 2.7. Програма як діалектичне заперечення проблеми 8 страница
4.6.2 Еквівалентність машин Тьюрінга та породжуючих граматик
Наведений у попередньому прикладі протокол машини Тьюрінга підказує ідею побудови породжуючої граматики за програмою машини. Таку побудову зробимо в два етапи: спочатку за програмою побудуємо продукції переходу (перетворення) конфігурацій машини Тьюрінга, потім зробимо обернення побудованих продукцій та добавимо правило для аксіоми та правила породження і видалення порожніх символів. Отримана породжуюча граматика буде еквівалентна вибраній машині Тьюрінга.
Кожна команда машини Тьюрінга породжує наступні правила перетворення конфігурацій:
· Команда виду qa®pbR породжує правило qa®bp.
· Команда виду qa®pbL породжує множину правил перетворення { cqa®pcb | сÎA}.
· Команда виду qa®pb породжує правило qa®pb.
На другому етапі побудови обернемо отримані правила (перетворення виду α→β замінимо на правило породжуючої граматики β→α), добавимо правило для аксіоми S®#qF#. Враховуючи, що при таких побудованих простих правилах можуть бути зайві #, переведемо їх в пустий ланцюжок e правилом #®e, або створимо у разі необхідності додаткові порожні символи # правилом #®##. Нарешті, потрібно буде видалити початковий стан, щоб отримати (породити) початковий ланцюжок правилом q0®e.
Таким чином, буде створена граматика GM=(N,T, P, S), яка має наступні параметри:
· N={S}ÈQÈ{#} (SÏ QÈ{#}).
· T=A\{#}.
· SÎN.
|
|
|
· P будується за вказаним вище алгоритмом.
Продемонструємо наведений алгоритм прикладом.
Приклад 4.15 Візьмемо машину Тьюрінга, запропоновану в попередньому прикладі, та побудуємо еквівалентну їй граматику. Отримаємо граматику GM =({ S, q0, qa, q-a, qb, q-b, qL, qF, #}, {a, b}, P, S).
Потрібні перетворення команд наведено в таблиці, третій стовбчик якої задає продукції P.
Таблиця 4.2
| Команди машини Тьюрінга | Правила перетворення конфігурацій | Продукції породжуючої граматики |
|
| 0. S ®#qF#
0#. # ®##
|
Правила, отримані перетворенням команди з номером n (n=6, 10, 11, 12) будемо далі нумерувати як n(1), n(2), n(3).
Продемонструємо коректність правил виводу для породження ланцюжка abba (індекси вказують на застосоване правило):
SÞ0#qF#Þ14#q0#Þ13#qL#Þ0##qL##Þ10(3) ##q-bb#Þ16#q-bb#Þ9#bqb#Þ8 #qbb#Þ0###q0b#Þ13#qL#bb#Þ12(3)##qLbb#Þ16#qLbb#Þ12(2) #bqLb#Þ0#
|
|
|
#bqLb##Þ6(2) #bbq-aa#Þ5#bbaqa#Þ3#bbqaa#Þ4#bqaba#Þ4#qabba#Þ1
#q0abba#Þ16 q0abba#Þ16 q0abba.
Зауважимо, що в процесі виводу застосувались правила породження та знищення порожнього символу #.
Наведені вище міркування та приклад дозволяють сформулювати наступне твердження.
Теорема 4.3 За кожною машиною Тьюрінга M можна побудувати еквівалентну їх породжуючу граматику G, що породжує ту ж мову, яку сприймає M, тобто: LT(M)=L(G).
Ця теорема може бути обернена.
Теорема 4.4 За кожною породжуючою граматикою G можна побудувати еквівалентну їх машину Тьюрінга M, що сприймає ту ж мову, яку породжує G, тобто: LT(M)=L(G).
Доведення може бути конструктивним, коли машиною Тьюрінга моделюється зворотній до породження процес сприйняття ланцюжка, або можна скористатись тезою Чорча, що стверджує існування машини Тьюрінга для формального подання інтуітивних алгоритмів. Тут деталі такої побудови описувати не будемо.
З теореми випливає, що граматики типу 0 породжують усі рекурсивно-зліченні множини (мови) в алфавіті A. Тим самим клас породжующих граматик має таку ж виразну потужність, як і інші універсальни моделі алгоритмів.
|
|
|
Відзначимо, що є різні варіанти машин Тьюрінга, наприклад, машини з різною кількістю стрічок, з різними обмеженнями на команди. Зокрема, виділяють детерміновані (не існує команд з однаковими лівими частинами та різними правими частинами), та недетерміновані машини Тьюрінга (існують команди з однаковими лівими частинами та різними правими частинами). Клас формальних мов, що сприймаються машинами Тьюрінга, є однаковий для детермінованих та недетермінованих машин, та для машин з різною кількістю стрічок.
4.6.3 Лінійно-обмежені автомати
Лінійно-обмежені автомати можуть розглядатися як обмежені машини Тьюрінга, коли довжина ланцюжка на стрічні завжди лінійно обмежена довжиною вхідного ланцюжка.
Визначення 4.28 Машина Тьюрінга M =(Q, A, #, d, q0, F) називається лінійно-обмеженим автоматом, якщо існує число k, що для будь якого ланцюжка v 
A* довжини n, з умови #q0v# |–* #w1q w2# (qÎQ, w1, w2Î A*) випливає, що |w1 w2| 
k×n.
Наведену умову важко перевірити, маючи машину Тьюрінга, тому наведене визначення часто спрощують, вимагаючи, щоб k=1, тобто, щоб голівка машини Тьюрінга не могла записувати нові символи за межами вхідного ланцюжка. Є і інші варіанти визначення лінійно-обмежених автоматів.
|
|
|
Використовуючи методи, наведені в попередньому підрозділі, можемо за лінійно-обмеженим автоматом побудувати еквівалентну породжуючу граматику типу 1, і навпаки, за граматикою типу 1 побудувати лінійно-обмежений автомат. Таким чином, справедливе наступне твердження.
Теорема 4.5 За кожним лінійно-обмеженим автоматом можна побудувати еквівалентну йому породжуючу граматику типу 1, і навпаки, за кожною породжуючою граматикою типу 1 можна побудувати еквівалентний їй лінійно-обмежений автомат.
Говорячи більш просто, теорема стверджує, що клас лінійно-обмежених автоматів еквівалентний класу породжуючих граматик типу 1.
4.6.4 Магазинні автомати
Магазинні автомати (автомати з магазинною пам’яттю, МП-автомати, стекові автомати) широко використовуються в програмуванні, бо дозволяють моделювати різні важливі алгоритми, які повязані з компіляцією та інтерпретаціює мов програмування, обробки складних структур даних – дерев, списків і таке інше. Такі автомати можна розглядати як обмежені машини Тьюрінга, що мають вхідну стрічку, на якій голівка може тільки читати символи і рухатись тільки в один бік, та робочу стрічку, яку відповідна голівка може обробляти лише з однієї сторони. Як і в попередніх випадках є різні варіанти визначень магазинних автоматів. Наведемо тут просте екстенсіональне визначення, яке разом з тим є еквівалентним іншим визначенням за класом мов, що розпізнаються.
Визначення 4.29 Магазинний автомат – це шістка M =(Q, A, Γ, d, q0, F), де
· Q – скінченна множина станів,
· A – скінченний вхідний алфавіт (QÇA=Æ),
· Γ – скінченний магазинний алфавіт,
· d – скінченне відношення переходів (скінченне відображення d:Q´A´G®Q´G*),
· q 0 – початковий стан із Q,
· F – підмножина фінальних (заключних) станів із Q.
Виконання команди виду (q, a, Z)®(p, g) означає, що знаходячись у стані q, та оглядаючи символ a на вхідній стрічці, і символ Z у магазині, автомат переходить у стан p, стирає символ a та пересуває голівку до наступного символу на вхідній стрічці, а замість символу Z записує у магазин ланцюжок g. Зауважимо, що в інших модифікаціях магазинних автоматів перехід в новий стан може відбуватися без стирання символа із вхідної стрічки (так званий e-перехід).
Конфігурацію магазинного автомату можна задати як трійку (q, w, z), де qÎQ, wÎ A*, zÎG*). Відношення безпосереднього переходу |– задається так: (q, aw¢, Zz¢)|– (p, w¢, gz¢), якщо команда (q, a, Z)®(p, g) належить d.
Аналогічно тому, як це робилось раніше, визначаються і інші необхідні поняття, пов’язані з магазинним автоматом: протоколи та мова, що сприймається таким автоматом.
Для нас важливим є наступне твердження.
Теорема 4. 6 За кожним магазинним автоматом можна побудувати еквівалентну йому породжуючу граматику типу 2 (контекстно-вільну граматику), і навпаки, за кожною породжуючою граматикою типу 2 можна побудувати еквівалентний їй магазинний автомат.
Зважаючи на те, що синтаксис мов програмування, як правило, задається граматиками типу 2, теорема стверджує, что алгоритми обробки програм можуть базуватися на магазинних автоматах.
4.6.5 Скінченні автомати
Скінченні автомати можна розглядати як обмежені машини Тьюрінга, що мають одну вхідну стрічку – голівка може тільки читати символи і рухатись тільки в один бік. Тому такі автомати не мають необмеженої пам’яті. Екстенсіональне визначення наступне.
Визначення 4.30 Скінченний автомат – це п’ятірка M =(Q, A, d, q0, F), де
· Q – скінченна множина станів,
· A – скінченний вхідний алфавіт (QÇA=Æ),
· d – скінченне відношення переходів (скінченне відображення d:Q´A®Q),
· q 0 – початковий стан із Q,
· F – підмножина фінальних (заключних) станів із Q.
Всі основні загальні (інтенсіональні) поняття визначаються подібно до того, як це було зроблено для машин Тьюрінга та магазинних автоматів, тому тут їх наводити не будемо.
Основним є наступний результат.
Теорема 4.7 За кожним скінченним автоматом можна побудувати еквівалентну йому породжуючу граматику типу 3 (ліволінійну чи праволінійну граматику), і навпаки, за кожною породжуючою граматикою типу 3 можна побудувати еквівалентний їй скінченний автомат.
Відзначимо, що детермінованість чи недетермінованість скінченного автомату не впливає на клас мов, що сприймаються автоматами.
Теорія скінченних автоматів розроблена досить детально, для них побудовані алгоритми еквівалентних перетворень, мінімізації та таке інше. Тут наведемо лише один результат, що стосується алгебраїчного подання скінченно-автоматних мов. Такі мови ще називаються регулярними мовами.
Регулярні мови задаються виразами (термами) регулярної алгебри мов, що має операції об’єднання, конкатенації та ітерації.
Регулярні вирази можна визначити індуктивно.
Базис складається з трьох визначень.
1. Константи ε та Ø є регулярними виразами.
2. Якщо a – довільний символ, то a – регулярний вираз. Зауважимо, що часто в написанні розрізняють символ алфавіту та відповідний вираз. Тут це не робимо, щоб не ускладнювати текст.
3. Якщо X – змінна, то X – регулярний вираз.
Крок індуктивної побудови. Індуктивний крок складається з чотирьох визначень, по одному для трьох операторів та для введення дужок.
1. Якщо E та F – регулярні вирази, то E+F - регулярний вираз.
2. Якщо E та F – регулярні вирази, то EF – регулярний вираз. Зауважимо, що для позначення оператора конкатенації – як операції над мовами, так і оператора в регулярному виразі – можна використовувати крапку.
3. Якщо Е – регулярний вираз, то Е* - регулярний вираз.
4. Якщо Е – регулярний вираз, то (Е) – регулярний вираз.
Інтерпретація L виразів в класі мов над алфавітом A задається також індуктивно на підставі інтерпретації змінних LV: Var ®2A*, де Var – множина змінних.
Інтерпретація базових виразів задається таким чином:
1. L(ε) = {ε} і L(Ø) = Ø.
2. L(a) = {a}.
3. L(X) = LV(X).
Інтерпретація складних виразів задається таким чином (E та F – регулярні вирази):
1. L(E+F) = L(E) 
L(F).
2. L(EF) = L(E)L(F).
3. L(E*) = (L(E))* .
4. L((E)) = L(E).
Ми використовуємо L(E) для позначення мови, яка відповідає Е. Як і в інших алгебрах, оператори регулярних виразів мають певні пріоритети, тобто оператори зв‘язуються зі своїми операндами в певному порядку.
Найвищий пріоритет має оператор ітерації *. Далі йде оператор конкатенації. Оскільки він асоціативний, то не має значення, в якому порядку групуються послідовні конкатенації. Але, якщо необхідно групувати вирази, то робимо це, починаючи зліва. Найнижчий пріоритет має оператор об’єднання. Він також асоціативний. Для нього будемо притримуватися групування, починаючи з лівого краю виразу.
Основний результат стосовно регулярних мов є наступний.
Теорема 4. 8 За кожним скінченним автоматом можна побудувати еквівалентний йому регулярний вираз, і навпаки, за кожним регулярним виразом можна побудувати еквівалентний йому скінченний автомат.
Наведений результат дозволяє використовувати різні формалізми (граматики типу 3, скінченні автомати, регуляні вирази) для дослідження властивостей регулярних мов. Такі мови мають гарні властивості замкненості (відносно об’єднань, перетину, доповнень, конкатенації, ітерації та деяких інших операцій). Ще одну важливу групу властивостей регулярних мов становлять «властивості розв’язності». За їх допомогою можна з’ясувати, чи визначають два різні автомати одну і ту саму мову. Розв’язність цієї задачі дозволяє мінімізувати автомати, тобто за даним автоматом знайти еквівалентний йому з найменшою можливою кількістю станів. Задача мінімізації має велике значення при проектуванні інтегральних схем.
Дата добавления: 2019-02-13; просмотров: 218; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!