Малюнок 2.7. Програма як діалектичне заперечення проблеми 7 страница

Теорема 4.2 Для довільної породжуючої граматики G₀ існує граматика G_C у загально-контекстній формі, яка породжує ту саму мову, тобто L(G₀)=L(G_C).

Визначення 4.22 Довільні граматики G₁ та G₂ називаються еквівалентними, якщо вони породжують одну й ту саму мову, тобто G₁ » G₂ Û L(G₁)=L(G₂).

Цілком очевидно, що так введенне відношення » є відношенням еквівалентності (рефлексивним, симетричним та транзитивним відношенням).

Приклад 4.13 Побудуємо за граматикою G3, що породжує мову L(G3)={aⁿbⁿcⁿ|n³0} еквівалентну їх загально-контекстну граматику G3_C.

Граматика G3 має наступні правила:

P1: S ® aBSc

P2: S ® e

P3: Ba ® aB

P4: Bb ® bB

P5: Bc ® bc

З них неконтекстними є правила P3 та P4. Спочатку перетворемо правило Ba®aB (правило P3) в послідовність контекстних правил. Отримуємо:

Ba®aB замінуємо на BA_a®A_aB, A_a®a.

Далі замість BA_a®A_aB вводимо послідовність правил

BA_a®N₃₁A_a

N₃₁A_a ®N₃₁N_3r

N₃₁N_3r®N_3pN_3r

N_3pN_3r®N_3pA_aB

N_3p®e

Аналогічно поступаємо з правилом P4: Bb ® bB. Після цих перетворень отримуємо нову граматику G3_C, в якій пронумеруємо нові правила:

P1: S ® A_aBSc,

P2: S ® e

P31: A_a®a

P32: BA_a®N_3lA_a

P33: N_3lA_a ®N_3lN_3r

P34: N_3lN_3r®N_3pN_3r

P35: N_3pN_3r®N_3pA_aB

P36: N_3p®e

P41: B_b ® b

P42: BB_b®N_4lB_b

P43: N_4lB_b ®N_4lN_4r

P44: N_4lN_4r®N_4pN_4r

P45: N_4pN_4r®N_4pB_bB

P46: N_4p®e

P5: Bc ® B_bc

Побудуємо декілька виводів в цій граматиці, тобто, говорячи в термінах програмування, зробимо «тестування» побудованої граматики.

Очевидно, що S e та S A_aBSc A_aBc A_aB_bc aB_bc abc. Побудуємо вивід ланцюжка a²b²c². Маємо,  

S  A_aBSc  A_aBA_aBScc  A_aBA_aBcc  A_aBA_aB_bcc  A_a N_3lA_aB_bcc  

A_a N_3lN_3rB_bcc  A_a N_3pN_3rB_bcc  A_a N_3p A_aBB_bcc  A_aA_aBB_bcc  A_aA_aN_4lB_bcc A_aA_aN_4lN_4rcc A_aA_aN_4pN_4rcc A_aA_aN_4pB_bBcc  A_aA_aB_bBcc  A_aA_aB_bB_bcc  A_aA_aB_bbcc  A_aA_abbcc  A_aabbcc   aabbcc.

 

Еквівалентність нескорочуючих та контекстно-залежних граматик доводиться аналогічним чином.

Це дозволяє нам говорити про те, що різні варіанти визначень граматик (породжуючі та конктекстні) є еквівалентними, і що ієрархія Хомского досить стабільна відносно варіантів граматик.

Перейдемо до дослідження зв’язків класів породжуючих граматик з класами формалізмів розпізнання (сприйняття), в першу чергу, с класами автоматів різного типу.

 

4.6 Автоматні формалізми сприйняття мов

Дуальним методом до породження мов є їх сприйняття (розпізнавання). Цей метод також може уточнюватись на основі поняття транзиційної системи. Відмінність полягає у тому, що початковий стан містить ланцюжок, для якого потрібно перевірити його належність певній мові, а заключний стан говорить про належність (або неналежність) мові.

Існують різні уточнення методів сприйняття. Одним з них є уточнення, яке можна отримати з породжуючих граматик простим оберненням застосування правил, тобто замість правила породжуючої граматики α→β розглядати правило сприймаючої граматики β→α. Вивід в сприймаючій граматиці тоді треба вести від термінального ланцюжка до аксіоми. Такий метод уточнення нічого суттєво нового не привносить, хоча він часто розглядається в теорії формальних граматик як метод висхідного аналізу. Тому важливо визначити інші формалізми сприйняття мов. З цією метою часто обираються формалізми автоматів (машин) різного типу.

Автомати характеризуються тим, що відбувається розподіл на інформацію, що зберігається у пам’яті певного типу, та на інформацію, що керує процесом функціонування автомату і яка задається керуючим пристроєм автомату. Такий розподіл корисний тим, що робить функціонування автомату більш детермінованим. Іншими словами, формалізм автоматів більш пристосований до керування виводом ніж формалізм граматик, де керування виводом дуже слабке.

Автомат в його загальній формі має пам’ять (як правило, це потенційно нескінченна стрічка), має пристрій керування (задається скінченною множиною станів), та керуючу голівку, яка «працює» з певним елементом пам’яті. Головним для автомату є спосіб його функціонування, який задається переходами із стану в стан, зміною пам’яті та рухом голівки. Ці переходи залежать від поточного стану керування та змісту елементу пам’яті, на який «дивиться» голівка.

Є різні варіанти визначень автоматів. Розглянемо ті з них, що відповідають класифікації мов за Хомським.

Найбільш потужними за сприймаючою силою є автомати, що називаються машинами Тьюрінга.

4.6.1 Машини Тьюрінга

Машина Тьюрінга M складається з таких частин.

1. Керуючий пристрій, який може приймати певний стан з скінченної множини Q.
2. Стрічка (потенційно) нескінченої довжини, розділена на комірки, в яких розміщена вхідна інформація у вигляді символів деякого алфавіту A (як правило, QÇA=Æ). В кожній комірці записано по одному символу з алфавіту. Виділяється особливий символ #ÎA, який інтерпретуємо як “порожній символ”, причому в кожен даний момент стрічка містить лише скінчену кількість символів, відмінних від #. Вважаємо також, що всі такі “непорожні” символи записані підряд.
3. Голівка читання-запису забезпечує обмін інформацією між стрічкою і керуючим пристроєм. В кожний момент часу голівка може працювати тільки з однією коміркою стрічки. Голівка може

· замінити прочитаний символ іншим символом алфавіту A,

· переміщуватись на одну позицію вправо чи вліво, чи

· залишатись на місці.

Робота машини задається спеціальними правилами переходу (командами), що називаються програмою машини.

Програма складається з команд виду qa®pbR, qa®pbL, qa®pb (q, pÎQ, a, bÎA, L,R – додаткові символи). Інтерпретація команд наступна:

· Виконання команди qa®pbR. Якщо керуючий пристрій знаходиться у стані q, а голівка оглядає комірку на стрічці, у якій записано символ a, то керуючий пристрій переходить у стан p, голівка у комірку записує символ b і сама зміщується на одну комірку вправо.

· Виконання команди qa®pbL. Відрізняється від попереднього лише тим, що голівка зміщується вліво.

· Виконання команди qa®pb. Відрізняється від попередньої команди тим, що голівка залишається на місці.

В подальшому не будемо акцентувати увагу на керуючому пристрої та голівці і говорити просто, що машина Тьюрінга змінує свій стан та рухається вліво або вправо.

У фіксований момент часу поточна інформація задається за допомогою конфігурації машини Тьюрінга. Конфігурацією машини Тьюрінга зазвичай називається трійка (q, #w, v#), де qÎQ, w,v ÎA*. Конфігурація описує повний стан машини і інтерпретується таким чином:

· q – стан керуючого пристрою,

· #w – ланцюжок, записаний на стрічні машини вліво від голівки,

· v# – ланцюжок, записаний на стрічні машини вправо від голівки, включаючи символ, який оглядає голівка.

Зважаючи на те, що будемо перетворювати команди машини Тьюрінга у правила граматики, конфігурації в подальшому будемо задавати у вигляді ланцюжка #wqv# (тому тут важливо, щоб QÇA=Æ).

Оскільки машина Тьюрінга є конкретизацією транзиційної системи, то у визначення вводиться початковий стан q₀ÎQ та множина заключних станів FÍQ. Звичайним чином вводиться відношення безпосереднього виводу Þ (часто позначається |–) та рефлексивне транзитивне замикання цього відношення Þ* (|–*). Введені поняття дають можливість формального визначення машин Тьюрінга.

Визначення 4.23 Машиною Тьюрінга M називається послідовність параметрів (Q, A, #, d, q _{0, F}), де

· Q – скінченна множина станів,

· A – скінченний алфавіт (QÇA=Æ),

· # – символ з A («порожній» символ),

· d – скінченна множина команд qa®pbR, qa®pbL, qa®pb (q, pÎQ, a, bÎA, L,R – додаткові символи),

· q ₀ – початковий стан із Q,

· F – підмножина фінальних станів із Q.

Зауважимо, що є багато варіантів визначення машин Тьюрінга, наприклад, може бути декілька стрічок, порожній символ можна явно не вводити в алфавіт і вважати його однаковим для класу машин Тьюрінга, не вводити заключних станів і таке інше. Всі такі визначення, як правило, є еквівалентними з точки зору сприйняття мов.

Наведене визначення задає екстенсіонал поняття машини Тьюрінга, тобто клас одиничних машин. Що стосується інтенсіоналу, то він обумовлений призначенням машин, орієнтованих на сприйняття мов, яке засновано на відношенні |–_T (Þ_T) безпосереднього переходу від однієї конфігурації до іншої.

Визначення 4.24 Конфігурацією машини Тьюрінга M =(Q, A, #, d, q₀, F) називається ланцюжок виду #wqv#, qÎQ, w,v ÎA*.

Визначення 4.25 Нехай M =(Q, A, #, d, q₀, F) – машина Тьюрінга. Конфігурація #wcqav# безпосередньо переходить

· в конфігурацію #wcbpv#, якщо виконується команда qa®pbR,

· в конфігурацію #wpcbv#, якщо виконується команда qa®pbL, та

· в конфігурацію #wcpbv#, якщо виконується команда qa®pb (a,b,cÎA, w,v ÎA*, q, pÎ Q).

Ми будемо відношення безпосереднього переходу також називати відношенням виводу конфігурацій, щоб продемонструвати його єдність з відношенням виводу у породжуючих граматиках та формальних системах. Послідовність конфігурацій, пов’язаних відношенням безпосереднього виводу, називається протоколом машини Тьюрінга.

Визначення 4.26 Рефлексивне транзитивне замикання відношення |–_T позначаємо |–*_T.

Початкові конфігураціі мають вид #q₀v#, фінальні – #w₁q_Fw₂# , q_FÎF.

І, нарешті, головне смислове визначення.

Визначення 4.27 Мова, яка допускається машиною Тьюрінга M =(Q, A, #, d, q₀, F), є множина ланцюжків

L_T(M)={ w| #q₀w #|–*_T #w₁q_F w₂#, q_FÎF, w, w₁,w₂Î A*}

Таким чином, поняття машини Тьюрінга є єдністю двох аспектів: екстенсіонального та інтенсіонального. Екстенсіональний аспект задається як клас машин Тьюрінга, визначених відповідними шістками параметрів, інтенсіональний аспект задається уніформними визначеннями відношенням безпосередньої вивідності, та мови, що сприймається (допускається, розпізнається) машиною.

Приклад 4.14 Побудуємо машину Тьюрінга, яка допускає мову { | rÎ{a,b}*}.

Ідея програми наступна:

1. В початковому стані q₀ машина читає символ a, b, або #. У перших двох випадках машина стирає прочитані символи та «запам’ятовує» прочитаний символ відповідно у стані q_a або у стані q_b. Останній випадок означає, що на вхідній стрічці – порожній ланцюжок і тому машина переходить в заключний стан q_F.
2. Далі голівка рухається у правий бік до кінця ланцюжка. Прочитавши порожній символ # голівка повертається на одну комірку (клітинку) вліво та переходить у стан q_-a зі стану q_a, або у стан q_-b зі стану q_b. Тут індекси –a та –b означають, що машині потрібно зтерти відповідно символ a або b.
3. Якщо правий символ ланцюжка співпадає з символом, «запам’ятованим» як такий, що потрібно стерти, то він стирається, машина переходить у стан q_L.
4. У стані q_L голівка рухається вліво, поки не дійде до символу #. Далі голівка переходить у стан q₀ та сміщуються у правий бік. Один цикл перевірки завершено. Робота продовжується наступним циклом перевірки або завершується, якшо все перевірено.

Наведений алгоритм дозволяє побудувати машину Тьюрінга

M =({ q₀, q_a, q_-a, q_b, q_-b, q_L, q_F}, {a, b}, #, d, q ₀, {q_F}),

де d – множина наступних команд:

1. q₀a®q_a#R

2. q₀b®q_b#R

3. q_aa®q_aaR

4. q_ab®q_abR

5. q_a#®q_-a#L

6. q_-aa®q_L#L

7. q_ba®q_baR

8. q_bb®q_bbR

9. q_b#®q_-b#L

10. q_-bb®q_L#L

11. q_La®q_LaL

12. q_Lb®q_LbL

13. q_L#®q₀#R

14. q₀#®q_F#

 

Розглянемо на прикладі сприйняття слів цією машиною Тьюрінга. Візьмемо слово #abba#. Побудуємо протокол його сприйняття:

#q₀abba#Þ#q_abba#Þ#bq_aba#Þ#bbq_aa#Þ#bbaq_a#Þ

#bbq_-aa#Þ#bbq_L#Þ #bq_Lb#Þ# q_Lbb#Þ q_L#bb#Þ

# q₀bb#Þ# q_bb#Þ# bq_b#Þ #q_-bb#Þ#q_L#Þ#q₀#Þ#q_F#

---

Дата добавления: 2019-02-13; просмотров: 260; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!