Подання мов

Перш ніж перейти до головного викладу, розглянемо деякі фунда­ментальні питання стосовно множин ланцюжків.

Нехай А та В є підмножинами V*, деV— алфавіт. Конкатенацією множин А та В (позначаютьАВ) називають множину всіх ланцюж­ків вигляду α β, де α є ланцюжком з множини А, а β — ланцюжком з множини В.

Приклад 9.30. Нехай A ={0, 11} та B ={ 1, 10, 110}. Знайдемо множини АВ таВА.

Множина АВ містить кожну конкатенацію ланцюжка з А і ланцюжка з В, отже,

AB ={01, 010, 0110, 111, 1110, 11110}.

Множина ВА містить кожну конкатенацію ланцюжка з В і ланцюжка з А, отже,

BА ={10, 111, 100, 1011, 1100, 11011}.▲

Звернемо увагу, що загалом АВ≠ ВА.

З використанням означення конкатенації двох множин ланцюж­ків можна дати означення степеня множини ланцюжків Аⁿ для n =0, 1, 2,... Це роблять за допомогою рекурсії:

A⁰={λ };

Aⁿ⁺¹=AⁿA; для n =0, 1, 2,...

Тут, як і раніше, λ позначає порожній ланцюжок.

Приклад 9.31. Нехай А={1, 00}. Знайдемо Аⁿ для n =1, 2 та 3.

Маємо А⁰={𝜆 } та А¹=А⁰А={𝜆 }А={1, 00}. Щоб знайти А² візь­мемо конкатенацію всіх пар елементів з А. Це дасть А²={11, 100, 001, 0000}. Для знаходження А³ треба взяти конкатенації елементів з А²та А, тоді одержимо:

A ³={111, 1100, 1001, 10000, 0011, 00100, 00001, 000000}. ▲

Нехай А є підмножиною V*. Замиканням Клінімножини А (поз­начають А^*) називають множину всіх ланцюжків, які можна утво­рити конкатенацією довільної кількості ланцюжків з А. Отже,

Приклад 9.32.Знайдемо замикання Кліні для множин A ={0}, B ={0, 1}та С ={1, 1}.

Замиканням Кліні множини А є конкатенація ланцюжка 0 з собою довільну скінченну кількість разів. Отже, А^*={0 ⁿ | п=0, 1, 2,...}. Зами­канням Кліні множини В є конкатенація довільної кількості лан­цюжків, де кожний ланцюжок є 0 або 1. Це не що інше, як множина всіх ланцюжків над алфавітом V ={0, 1}; отже, В^*=V^*. Нарешті, замикання Кліні множини С є конкатенацією ланцюжка 11 з собою довільну скінченну кількість разів. Отже, С^* є множиною ланцюж­ків з парною кількістю одиниць: C ^*={1^{2 n} | n =0, 1, 2,...}.▲

Скінченні автомати можна використовувати для подання мов (множин ланцюжків). Однак, які саме множини можна задавати цими автоматами? Цю проблему вперше вирішив американський математик С. Кліні (S. Кіеепе) 1956 р. Учений довів, що існує скінченний автомат, який допускає множину ланцюжків тоді й лише тоді, коли цю множину можна побудувати з порожньої множини (множини, що не містить жодного ланцюжка), множини, що містить тільки порожній ланцюжок, і множин, що містять один односимвольний ланцюжок з використанням операцій конкатенації, об'єднання та замикання Кліні у довільному порядку. Множини ланцюжків, які можуть бути побудовані таким способом, називають регулярними.

Перш, ніж точно означити регулярні множини, необхідно дати означення регулярних виразів.

Регулярний вираз над множиною І означують рекурсивно так:

символ∅ є регулярним виразом;

символ 𝜆 є регулярним виразом;

символ х є регулярним виразом, якщо х∈ I; вирази (АВ), (А ∪ В) та А ^* є регулярними, якщо А та В - регу­лярні.

Кожний регулярний вираз зображає множину ланцюжків, визна­чену за такими правилами:

∅ - порожню множину, тобто множину, яка не містить жодного ланцюжка;

λ - множину {λ }, що є множиною, яка містить лише порожній ланцюжок;

x - множину { x }, ця множина має один ланцюжок, який склада­ється з одного символу х;

(АВ) - конкатенацію множин, котрі зображені виразами А та В;

(А∪ В) - об'єднання множин, котрі зображені виразами А та В;

А* - замикання Кліні множини, яка зображена виразом А.

Множину, зображену регулярним виразом, називаютьрегу­лярною множиною. Відтепер регулярні вирази будемо використо­вувати для опису регулярних множин. Це означає таке: якщо ми посилатимемось на регулярну множину А, то маємо на увазі регу­лярну множину, яка зображена регулярним виразом А.

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

Приклад 9.33. У табл. 9.7 показано, з яких ланцюжків склада­ються регулярні множини, що зображені такими регулярними вира­зами: 10*, (10)*, 0∪ 01, 0(0∪ 1)* та (0*1)*.

Таблиця 9.7

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

Доведення. Доведемо лише необхідність. Доведення достат­ності складне й виходить за межі цієї книги. Зазначимо, що регу­лярну множину визначають у термінах регулярних виразів, яківизначені рекурсивно. Отже, ми доведемо, що будь-яку регулярну множину допускає скінченний автомат, якщо зробимо такі обґрунтування.

1. Доведемо, що ∅ розпізнається скінченним автоматом.

2. Доведемо, що {λ } розпізнається скінченним автоматом.

3. Доведемо, що {α } розпізнається скінченним автоматом, якщо а є символом з I.

4. Доведемо, що АВ розпізнається скінченним автоматом, якщо А та Врозпізнаються.

5. Доведемо, що А∪ В розпізнається скінченним автоматом, якщо А та Врозпізнаються.

6. Доведемо, що А* розпізнається скінченним автоматом, якщо А розпізнається.

Тепер розглянемо кожну з цих задач.

1. Множину ∅ розпізнає недетермінований автомат без заключ­них станів, зображений на рис. 9.15.

Рис. 9.15 Рис. 9.16

Рис. 9.17

2. Недетермінований автомат, який розпізнає {λ }, має початко­вим і заключним станами s ₀ (рис. 9.16).

3. Доведемо, що множина {а} розпізнається недетермінованим скінченним автоматом. Розглянемо автомат з початковим станом s ₀ і заключним станом s ₁. Потрібно, щоб був лише один перехід з s ₀ в s ₁коли на вхід подано символ а; ніяких інших переходів не повинно бути. Діаграму такого автомата зображено на рис. 9.17. Єдиний ланцюжок, який допускається цим автоматом, - це одно­символьний ланцюжок а.

4. Нехай множини ланцюжківАтьВрозпізнаються скінченним автоматом. Нехай А розпізнається M_A=(S_A, І, f _A, s _A, F_A)та В розпізнається M_B=(S_B, I, f_B, s_B, F_B).Побудуємо скінченний автомат M_AB=(S_AB, I, f_AB, s_AB, F_AB), який розпізнає AB, тобто конкатенацію множин А та В. Автомат М_АВ будують як послідовне з'єднання автоматів М_А та М_B. Отже, ланцюжок з множини А використовує стани М_АВ від s_A(початкового стану М_А) до s_B(початкового стану М_B). Ланцюжок з множини В використовує стани автомата М_АВ від s_Bдо заключного стану автомата М_АВ. Побудуємо таку конструкцію. НехайS_AB=S_A∪ S_B Початковий станs_ABзбігається зs_A.Множиназаключних станів F_АB збігається з множиною заключних станівавтомата М_B і додатково в F_ABвходить ще й стан s_AB, якщо й лише якщо𝜆 ∈ А∩ В.

Рис. 9.18

5. Побудуємо скінченний автоматM_{A∪ B}=(S_{A∪ B}, I, f_{A∪ B}, s_{A∪ B}, F_{A ∪ B}) який розпізнає A ∪ B. Цей автомат будуємо як паралельне з'єднання автоматів М_A та М _B. У цьому разі вводимо новий початковий стан s_{A ∪ B}. Нехай в автоматі М_А є перехід з початкового стануs_A у стан s_k, а в автоматі М_B - перехід із початкового стануs _B у стан s_m. Тоді в автоматі М_{А ∪ В} є перехід від s_{А ∪ В} до s_k і до s_m.

Нехай S _{A∪ B}=S_A∪ S_B ∪ { s _{A∪ B}}, де s _{A∪ B} - новий стан, який єпочатковим станом в автоматі M _{A∪ B}

Множина заключних станів F _{A∪ B} дорівнюєF_A∪ F_B ∪ { s _{A∪ B}}, якщо 𝜆 ∈ A∪ B, і дорівнює у протилежному випадку. Із описаноїпобудови зрозуміло, що ланцюжок із множини А переводить автомат М_{A ∪ B} із початкового стануs_{A∪ B} у заключний стан і ланцюжок із множини В переводить автомат M _{A∪ B}із початкового стану в заключний стан. На рис. 9.19 показано конструкцію автомата М_{A ∪ B}.

Рис. 9.19

6. Нарешті побудуємо автомат М_{А *}=(S_A*, I, f_{A *}, s_A*, F_{A *}), якийрозпізнає А * - замикання Кліні множини ланцюжків А. НехайS_A* містить усі стани з і додатковий станS_A*, який є початковим станом для нового автомата. Множина заключних станів F_{А *} містить всі стани з F_А і ще додатково початковий станs_A*, оскільки порожній ланцюжок λ повинен допускатись автоматом М _A*.

Для того, щоб була допущена конкатенація довільної кількості ланцюжків з А, уведемо в структуру автомата М_А* всі переходи автомата М_А, а також ще деякі нові переходи. Якщо є перехід зі стануs_A - початкового стану автомата М_А, то введемо в автоматі М_А*, аналогічний перехід зі стану s_А* з тим самим вхідним символом. Крім того, введемо переходи з кожного заключного стану автомата М_А у стани, в які є переходи зі стану s_A (і знову з тим самим вхідним символом).

Рис. 9.20

Тепер будь-який ланцюжок, який є конкатенацією ланцюжків з множини А, переведе стан s_A*в один із заключних станів, коли перший ланцюжок буде прочитаний, повернеться до одного з заключних станів, коли другий ланцюжок буде прочитаний, і цей процес продовжиться. Рис. 9.20 ілюструє використану тут конструкцію. ▲

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

Приклад 9.34. Побудуємо недетермінований скінченний авто­мат, який розпізнає регулярну множину 1*∪ 01. Послідовність потріб­них дій показана на рис. 9.21. Почнемо з побудови автомата, який розпізнає 1*. Для цього використаємо автомат, який розпізнає 1 і, після цього, конструкцію для М_А*, описану в доведенні теореми. Далі побудуємо автомат, який розпізнає 01, з використанням автоматів, які розпізнають 0 та 1 і конструкцію для М_АВ із доведення. Нарешті, з використанням конструкції M _{A∪ B} побудуємо автомат для 1*∪ 01. В автоматах, які послідовно отримують, стани позначають щоразу новими символами.

Зазначимо, що побудова виконана точно відповідно до схеми доведення теореми. Значно простіший автомат, який розпізнає цю саму мову, зображений на рис. 9.22. ▲

Автомат

Рис. 9.21

Рис. 9.22

Єтісний зв'язок між регулярними множинами і регулярними граматиками. Цей зв'язок розкриває теорема 9.3.

Теорема 9.3.Регулярна множина й лише вона породжується регулярною граматикою.

Доведення. Спочатку доведемо, що множина, яка породжується регулярною граматикою, є регулярною множиною. Нехай G=(V, Т, S, Р)- регулярна граматика, яка породжує множину L (G). Доведемо, що L (G) - регулярна множина. Для цього побудуємо недетермінований скінченний автомаM_{A∪ B}=(S, I, f, s₀, F), який розпіз­нає L (G). Множина станів S автомата М містить стан s_A для кожного нетермінального символуА граматикиG і ще стан який є заключ­ним станом. Початковий стан — це стан, який відповідає почат­ковому символу S граматики G.

Переходи в автоматі М утворюють на підставі продукцій грама­тикиG таким способом. Якщо в граматиці G є продукціяА→ а, то в автоматі М утворюють перехід зі стану s_А до заключного стану s_F для вхідного символу а. За наявності продукції А→ аВ утворюють перехід зі стану у стан для вхідного символуа. Множина F заключних станів автомата М містить стан s_F і, якщо є продукцією граматики G, то ще і стан s ₀. Тепер неважко переко­натись, що мова L (M), яка розпізнається побудованим автоматом М, збігається з мовою L (G), яка породжена граматикоюG, отже, L (М)= L (G). Це можна зробити перевіркою ланцюжків, які пере­водять автомат у заключний стан. Отже, ми побудували недетермі­нований скінченний автомат, який розпізнає множину, породжену регулярною граматикою G. Тепер регулярність цієї множини випливає з теореми 9.2.

Рис. 9.23

Перш ніж продовжити доведення, наведемо приклад описаної вище методики побудови скінченного автомата, який розпізнає ту саму множину, що і регулярна граматика.

Приклад 9.35. Побудуємо недетермінований скінченний автомат для задання мови, яка породжується регулярною граматикоюG=(V, Т, S, Р) деV=(0, 1, А, S), T ={0, 1}, а множинаР складається з таких продукцій:

.

Діаграма переходів для автомата, який розпізнає мовуL(G), зображена на рис. 9.23. У цьому автоматі s ₀ - стан, який відповідає початковому символу S граматики G, s ₁ - стан, який відповідає нетерміналуА, s ₂ - заключний стан.▲

Завершення доведення теореми 9.3. Покажемо, що якщо множина є регулярною, то існує регулярна граматика, яка її пород­жує. НехайМ-недетермінований скінченний автомат, який розпіз­нає цю множину (такий автомат існує за теоремою 9.2). Завжди можна вважати, що в автоматі M немає переходу в початковий стан s ₀ (див. задачу 35). Побудуємо регулярну граматикуG=(V, Т, S, Р). Кожний символ алфавітуV в граматиціG вводимо відповідно або до символу стану, або до вхідного символу автоматаМ.Множина T термінальних символів граматики G якраз і відповідає символам вхідного алфавіту I автомата М. Початковий символ S граматики G відповідає символу початкового стану s ₀ автоматаМ.

Множину Р продукцій граматикиG формуємо на підставі пере­ходів в автоматі М. Якщо стан s у разі вхідного символу а пере­ходить у кінцевий стан, то в множину Р вводимо продукцію де А_s - нетермінальний символ граматикиG, який відповідає стану s. Якщо стан s переходить у стан t у разі вхідного символу а, то в множину Р вводимо продукціюA_s→ аA_t.Продукцію S → λ вклю­чимо в Р якщо і тільки якщо λ ∈ L (G). Отже, продукції в граматиці G відповідають переходам в автоматі М. Тепер легко переконатись, що L (G)= L (M).▲

Приклад 9, 36. На рис. 9.24 зображено діаграму переходів скін­ченного автомата. Знайдемо регулярну граматику, яка породжує регулярну множину, розпізнавану цим автоматом.

ГраматикаG=(V, Т, S, Р)має алфавіт V ={ S, A, B, 0, 1}Т={0, 1}, нетермінальні символиS, А та В відповідають станамs₀, s₁ та s ₂ автомата. У граматиці G початковий символ S, а продукціями є

таВ→ 1. Усі ці продукції отримані так, як це описано у другій частинідоведеннятеореми 9.3.▲

Рис. 9.24

З теорем 9.2 та 9.3 як безпосередній наслідок випливає такий результат.

Теорема 9.4.Множина, яка розпізнається скінченним автоматом, є точно такою, ніби її породжувала регулярна граматика. Іншими словами, для того, щоб мова була регулярною, необхідно і достат­ньо, щоб вона розпізнавалась скінченним автоматом. ▲

З'ясуємо, що означає задати питання щодо деякої мови. Зазна­чимо, що типова мова нескінченна, і тому немає змісту наводити комусь ланцюжки цієї мови і задавати питання, яке потребує перевірки нескінченної множини ланцюжків. Набагато розумніше використовувати один із способів скінченного подання мови, а саме - детерміновані скінченні автомати, недетерміновані скінченні автомати, регулярні вирази. Очевидно, що подані одним із цих спо­собів мови регулярні.

Для мов типу 3. (регулярних) скінченний автомат є адекватною моделлю. Для більш складних мов адекватними є інші автоматні моделі, які відрізняються від скінченних автоматів нескінченністю пам'яті. Проте, на цю нескінченність, залежно від типу моделі й пов'язаної з нею мови, накладають різні обмеження. Пам'ять може бутимагазинною, тобто доступною лише з одного кінця (стек); такий автомат є адекватним поданням для мов типу 2. Пам'ять може бутилінійно обмеженою, тобто такою, що лінійно залежить від довжини слова, яке допускається. Зокрема, такі автомати розпізнають мови типу 1. Усі вказані обмеження на нескінченність пам'яті роблять ці моделі більш обмеженими у своїх можливостях, ніж машини Тьюрінга, які вивчаються у розділі 10. Машини Тьюрінга можна вважати автоматною моделлю мов типу 0. Однак, в основному машини Тьюрінга використовують для уточнення поняття алгоритму.

Розглянемо інструмент, для доведення нерегулярності деяких мов - теорему, яка називається " лемою про накачування" (" pumpinglemma"). Інша назва - " лема про розростання".

Теорема 9.5 (лема про накачування для регулярних мов). Нехай L- регулярна мова. Існує константа п (залежна відL)така, що кожний ланцюжок𝜶 ∈ L, який задовольняє нерівність |α |≥ n, можна розбити на три ланцюжки α =β γ ω так, що виконуються умови:

1) γ ≠ λ; 2) |β γ |≤ n; 3) для довільного k ≥ 0 ланцюжок β γ ^k ω ∈ L.

Це означає, що завжди можна знайти такий ланцюжок у недалеко від початку ланцюжка α, котрий можна " накачати". Отже, якщо ланцюжок у повторити довільну кількість разів або вилучити(k=0), то отриманий у результаті ланцюжок все одно буде належати мовіL.

Рис. 9.25

Доведення. Нехай L —регулярна мова. Тоді існує детермінований скінченний автомат М, для якогоL=L(М), тобто який розпізнає цю мову. Нехай кількість станів автомата М дорівнює п (константа, яка фігурує у формулюванні теореми). Припустимо, що послідовні стани, у які переходить автомат М під дією вхідного ланцюжка α, є s ₀, s_{i 1}, s_{i 2}, _…, s_im, де т= |α | - довжина ланцюжка α. За умовоютеореми, т≥ п, тому в списку s ₀, s_{i 1}, s_{i 2}, _…, s_im, який складається принаймні з n +1 стану, обов'язково є повторення (це випливає з принципу коробок Діріхле). Нехай перший стан, який повторю­ється, є s_r. Позначимо γ ту частину ланцюжка α, яка переводить автомат із стану s_r, коли він зустрічається перший раз, у стан s_r, коли він зустрічається другий раз. Позначимо β частину ланцюжка α перед γ, а ω - частину ланцюжка α після γ. Очевидно, що |γ |≥ 1 (отже, γ ≠ λ), і |β γ |≤ n (оскільки всі стани, що зустрічаються до другої появи різні). Більше того, ланцюжок β γ ^k ω для будь-якого цілого невід'ємногоk повинен переводити автомат точно у той самий заключний стан, що й ланцюжокβ γ ω. Справді, частина γ ^k ланцюжка просто β γ ^k ω переводить стани автомата уздовж петлі, яка починається і закінчується в стані s_r. Ця петля проходиться к разів (див. рис. 9.25). Таким чином, ланцюжки β γ ^k ω допускаються автоматом тому, що ланцюжок руш допускається, і, отже, всі вони належать мовіL(М).▲

Приклад 9.37, Довести, що мова L ={0 ^m 1 ^m | т=0, 1, 2,...} нерегу­лярна.

Від протилежного. Припустимо, що мова L регулярна. Нехай ланцюжок α =0 ^m 1 ^m, і |α |=2 m ≥ n. Тоді за лемою про накачування лан­цюжки α =0 ^m 1 ^m =β γ ω та β γ ^k ω належать мові L, причому γ ≠ λ. Тепер розглянемо такі міркування. Ланцюжок у не може містити одночас­но нулі та одиниці, оскільки γ ² тоді містив би 10 і ланцюжок β γ ²ω не належав би мові L. Таким чином, γ складається або тільки з нулів, або тільки з одиниць. Але тоді β γ ²ω містить або забагато нулів, або забагато одиниць і, отже, не належить L. Ця суперечність і доводить, що мова L нерегулярна. ▲

Лема про накачування для контекстно вільних мов подібна до леми про накачування для регулярних мов, але кожний ланцюжок α контекстно вільної мови L розбивають на п'ять частин і сумісно " накачують" другу і четверту з них.

Теорема 9.6(лема про накачування для контекстно вільних мов). НехайL - контекстно вільна мова. Тоді існує така константап(залежна від L), що якщо α - довільний ланцюжок з L, довжина якого |α |≥ n, то цей ланцюжок можна так розбити на п'ять ланцюж­ків α =, що виконуються умови:

1) |γ ω δ |≤ n (отже, середня частина не дуже довга);

2) γ δ ≠ λ (оскільки - ланцюжки, які потрібно " накачувати", ця умова стверджує, що хоча б один з них непорожній);

3) β γ ^k ω δ ^k η для всіх k ≥ 0 (два ланцюжки γ та δ можуть бути " накачані" довільну кількість разів, або вилучені, якщо k =0, і отри­маний ланцюжок β γ ^k ω δ ^k η ті також буде належати мовіL).▲

Приклад 9.38.Доведемо, що моваД={0^m1^m2^m| m=0, 1, 2,...} не є контекстно вільною.

Від протилежного. Припустимо, що мова L контекстно вільна. Тоді можна знайти ланцюжки β, γ, ω, δ та η такі, що хоча б один з γ та δ непорожній та β γ ^k ω δ ^k η для всіхk≥ 0 зображаються у вигляді 0 ^m 1 ^m 2 ^m. Спочатку відзначимо, що кожний з ланцюжків γ та δ може утворюватись тільки символом одного типу. Дійсно, якщо хоча б один з двох ланцюжків γ або δ утворений символами двох або трьох типів, то у ланцюжку β γ ²ω δ ²η порушений потрібний порядок символів, тобто він не є у вигляді 0 ^m 1 ^m 2 ^m. Отже, принаймні один символ (нехай, наприклад, 0) у ланцюжку γ δ відсутній. З другого боку, оскільки γ δ ≠ λ, то принаймні один символ (нехай 1) входить у γ δ. Тоді для великих k ланцюжок β γ ^k ω δ ^k η буде містити більше одиниць, ніж нулів, і, отже, не буде належати мові L. Це суперечить лемі про накачування для контекстно вільних мов. Звідси випливає, що мова L ={0 ^m 1 ^m 2 ^m | m =0, 1, 2,...} не є контекстно вільною.

Задачі

1. НехайV={S, А, В, а, b}, Т={а, b}. Знайти мову, породжену граматикоюG=(V, Т, S, Р) із зазначеною множиною Р продукцій:

а) Р={ S→ АВ, А→ аb, В→ bb };

б) Р={ S→ АВ, S→ аА, А→ a, В→ bа };

в) Р={ S→ АВ, S→ АА, А→ aВ, А→ аb, В→ b };

г) Р={ S→ АА, S→ В, А→ aaА, А→ аа, В→ bВ, В→ b };

д) Р = { S→ АВ, А→ аАb, В→ bВа, А→ 𝜆, B→ 𝜆 }.

2. Нехай задана граматикаG=(V, Т, S, Р), де V ={0, 1, S }, T ={0, 1}, Р={ S → 0S1, S→ 𝜆 }. Погрібно:

а) побудувати виведення для 0³1³;

б) довести, що ця граматика породжує мову {0 ^m 1 ^m | m =0, 1, 2,...}.

3. Задана граматикаG₁=(V, Т, S, Р)де V ={ S, 0, 1}, T ={0, 1}, множина продукційP={ S→ 0 S, S→ S 1, S→ 𝜆 }. Потрібно:

а) побудувати виведення для 0²1⁴;

б) довести, що ця граматика породжує мову {0 ^m 1 ^m | m, n =0, 1, 2,...}.

4. Задана граматикаG₂=(V, Т, S, Р) де V ={ S, А, 0, 1}, T ={0, 1}, множина продукційP={ S→ 0 S, S→ 1 A, S→ 1, A→ 1 A, A→ 1, S→ 𝜆 }. Потрібно:

а) побудувати виведення для 0²1⁴;

б) довести, що ця граматика породжує ту саму мову, що і граматика G ₁ із задачі 3.

5. Побудувати граматики, які породжують мови:

а) {01¹ⁿ | n= 0, 1, 2,...};

б) {01^{1 n}| n =0, 1, 2,...};

в) {0 ⁿ 1 ^m 0 ⁿ | m, n =0, 1, 2,...}.

6. Нехай V ={ S, А, В, а, b}, Т={а, b}. Множини продукційРзадані нижче. Визначити, чи єG=(V, Т, S, Р) граматикою типу 0, але не типу 1; граматикою типу 1, але не типу 2; граматикою типу 2, але не типу 3, або граматикою типу 3:

а) Р ={ S→ аАВ, А→ Вb, B→ 𝜆 };

б) P={S→ aA, А→ а, А→ b};

в) Р ={ S→ АВа, АВ→ а };

г) Р ={ S→ АВА, А→ аВ, В→ аb };

д) Р ={ S→ bА, А→ В, В→ а };

е) Р ={ S→ аА, аА→ В, В→ аА, А→ b };

ж) Р ={ S→ bA, А→ b, S→ 𝜆 };

и) Р ={ S→ аВ, В→ аАb, аАb→ b };

к) P ={ S→ aA, А→ bВ, В→ b, В→ 𝜆 };

л) Р ={ S→ A, А→ В, В→ 𝜆 }.

7. Паліндромом називають ланцюжок, який однаково читається у прямому і зворотному напрямках. Знайти контекстно вільну гра­матику, яка породжує всі паліндроми над алфавітом {0, 1}.

8. Нехай G - граматика з V ={ a, b, с, S }, Т={а, b, с}, S - початковий символ і множина продукцій Р ={ S→ аbS, S→ bcS, S→ bbS, S→ a, S→ cb }. Побудувати дерево виведення для кожного з ланцюжків:

а)bсbbа; б) bbbсbbа; в) bсаbbbbbсb.

9. НехайG- граматика зV={а, b, с, А, В, С, S}, Т={а, b, с}, S - початковий символ і множина продукцій Р={S→ АВ, А→ Са, В→ Ва, В→ Сb, В→ b, С→ сb, С→ b}.Використати граматичний розбір звер­ху вниз для визначення, чи належить кожний з ланцюжків а - г мові, яка породжується цією граматикою:

а) bаbа; б) аbаb; в) сbаbа; г) bbbсbа.

10. Розв'язати задачу 9 з використанням граматичного розбору знизу вверх.

11. Побудувати діаграму станів для скінченного автомата з виходом, заданого таблицею станів (див. табл. до зад. 11).

12. Побудувати діаграму станів для скінченного автомата з виходом, заданого таблицею станів (див. табл. до зад. 12).

13. Побудувати діаграму станів для скінченного автомата з виходом, заданого таблицею станів (див. табл. до зад. 13).

Табл. до задачі 11

Табл. до задачі 12

Табл. до задачі 13

14. За діаграмою станів скінченного автомата з виходом побуду­вати таблицю станів.

15. За діаграмою станів скінченного автомата з виходом побудувати таблицю станів.

16. За діаграмою станів скінченного автомата з виходом побудувати таблицю станів.

17. Побудувати скінченний автомат з виходом, який затримує вхідний ланцюжок з нулів та одиниць на 2 розряди та видає перші 00 у вихідному ланцюжку.

18. Побудувати скінченний автомат з виходом, у якого вхідний алфавіт {0, 1, q}, а вихідний - {0, 1, even, odd}. Вихідний ланцюжок з 0 та 1 збігається з вхідним, а на кожний символ запитуqна виході видаєтьсяeven- якщо кількість 1 від початку роботи автомата парна, іodd - якщо непарна.

19. Побудувати скінченний автомат для реалізації процедури входу в систему. Користувач уводить ідентифікаційний номер, а потім - на відповідний запит - пароль. Якщо ідентифікаційний номер або пароль некоректні, то виводиться запит ідентифікацій­ного номера користувача. Ідентифікаційний номер і пароль для спрощення вважати односимвольними.

20. Побудувати скінченний автомат з вхідним і вихідним алфавітами {0, 1}. Автомат видає на виході 1, якщо три останні символи на вході були 101, і видає 0 у всіх інших випадках.

21. Визначити, які з ланцюжків а - г допускає скінченний автомат без виходу.

a)010; б) 1101; в) 1111110; г)010101010.

22. Знайти мову, яку розпізнає скінченний автомат без виходу. Діаграми станів а – г.

23. Знайти мову, яку розпізнає недетермінований скінченний автомат. Діаграми станіва-г.

г

24. Для кожного з недетермінованих скінченних автоматів задачі 23 побудувати детермінований скінченний автомат, який розпізнає ту саму мову.

25. Побудувати детерміновані скінченні автомати, які розпіз­нають мови:

а) {0}; б) {1, 00}; в) {1 ⁿ | n =2, 3, 4, }.

26. Побудувати недетерміновані скінченні автомати, які розпіз­нають мови задачі 25 і, якщо можливо, мають менше станів, ніж детерміновані автомати, побудовані в цій задачі.

27. Описати, з яких ланцюжків складаються регулярні множини:

а) 1*0; б) 1*00*; в) 111∪ 001; г)(1∪ 00)*; д) (00*1)*.

28. Визначити належність ланцюжка 1011 до регулярної множини:

а) 10*1*; б) 0*(10∪ 11)*; в) 1(01)*1*; г) 1*01(0∪ 1); д) 1(00)*(11)*;

е) (1∪ 00)(01∪ 0)1*.

29. Побудувати недетерміновані скінченні автомати, які розпіз­нають мови а - в:

а){λ, 0}; б) {0, 11}; в) {0, 11, 000}.

30. З використанням конструкцій, описаних у доведенні теореми 9.2 (теореми Кліні), побудувати недетерміновані скінченні авто­мати, які розпізнають регулярні множини:

а)0*1*; б) (0∪ 11)*; в)01*∪ 00*1.

31. Побудувати недетермінований скінченний автомат, який розпізнає мову, що породжена регулярною граматикою G ={ V, T, S, P }, де V={0, 1, S, A, B }, T ={0, 1}, S - початковий символ, а множина продукцій задана нижче:

а) P ={ S→ 0 A, S→ 1 B, A→ 0, B→ 0};

б) Р={ S→ 1 A, S→ 0, S→ 𝜆, А→ 0 В, B→ 1 B, В→ 1};

в) P={ S→ 1 B; S→ 0, А→ 1 А, A→ 0 В, А→ 1, A→ 0, В→ 1}.

32. Побудувати граматикуG={V, Т, S, Р}, яка породжує мову, розпізнавану скінченим автоматом а - в:

б

в

33. Показати, що скінченний автомат, побудований на основі регулярної граматики в доведенні теореми 9.3, розпізнає множину, що породжується цією граматикою.

34. Показати, що регулярна граматика, побудована на підставі скінченного автомата в доведенні теореми 9.3, породжує множину, яку розпізнає цей автомат.

35. Довести, що для кожного недетермінованого скінченного автомата існує еквівалентний недетермінований скінченний авто­мат, у якому немає переходу в початковий стан

36. Нехай М=(S, I, f, s₀, F) недетермінований скінченний автомат. Довести, що моваL(М), яка допускається цим автоматом, нескін­ченна тоді й лише тоді, коли існує ланцюжок х, який допускається автоматом М, і l (x)≥ |S|.

37. Використайте лему про накачування для регулярних мов, щоб довести нерегулярність таких мов:

а) {0 ^2m 1 ^m | m =0, 1, 2,...};

б) множина ланцюжків, утворених " збалансованими" дужками " (" та")", які зустрічаються у правильно побудованому арифметич­ному виразі;

в) {0 ^т 1 ^п 2 ^т|m, n= 0, 1, 2,...};

г) {0 ⁿ 1 ^m | n ≤ m };

д) {l ⁿ | n - повний квадрат};

е) {1 ⁿ |n- повний куб};

ж) {1ⁿ|п- степінь числа два};

и) множина паліндромів над алфавітом {0, 1};

к){1 ^p | p - просте число}.

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

а) { a^mbⁿc^k | m ≤ n ≤ k };

б) { аⁿbⁿс^m |m≤ n };

в) {1^p|p- просте число}.

39. Побудувати недетермінований скінченний автомат, який розпізнає ключові словаwebтаebey.

40. Перетворити недетермінований скінченний автомат із задачі39у детермінований скінченний автомат.