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

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

Покажемо, з яких ланцюжків утворено регулярні множини, задані регулярними виразами 10*, (10)*, 001, 0(01)* та (0*1)*:

Вираз	Ланцюжки, з яких складається відповідна регулярна множина
10*	1, а потім довільна кількість 0 (або без нулів)
(10)*	Довільна кількість повторень 10 (включно з порожнім ланцюжком)
001	Ланцюжок 0 і ланцюжок 01
0(01)*	Довільний ланцюжок, який починається з 0
(0*1)*	Довільний ланцюжок, який закінчується 1

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

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

Теорема 38.3. Регулярна граматика породжує регулярну множину й лише її.

Доведення. Спочатку доведемо, що множина породжена регулярною граматикою, регулярна. Нехай G = (V, T, S, P) – регулярна граматика, яка породжує множину L(G). Доведемо, що L(G) – регулярна множина. Для цього побудуємо недетермінований скінченний автомат M = (S, I, f, s₀, F), який розпізнає множину L(G). Множина станів S автомата M містить стан s_A для кожного нетермінального символу A граматики G та заключний стан s_F. Початковий стан s₀ відповідає початковому символу S граматики G.

Переходи в автоматі M утворимо за допомогою продукцій граматики G таким способом. Якщо в граматиці є продукція Aa, то в автоматі M має бути перехід зі стану s_A до заключного стану s_F для вхідного символу a. За наявності продукції AaB утворюють перехід зі стану s_A до стану s_B для вхідного символу a. Множина F заключних станів автомата M містить стан s_F і, якщо S  продукція граматики G, то ще й стан s₀. Тепер неважко переконатись, що мова L(M), яку розпізнає побудований автомат M, збігається з мовою L(G), породженою граматикою G. Отже, L(M) = L(G). Це можна зробити, перевіривши ланцюжки, які переводять автомат у заключний стан. Отже, ми побудували недетермінований скінченний автомат, який розпізнає множину, породжену регулярною граматикою G. Тепер регулярність цієї множини випливає з теореми 38.2.

Доведемо, що для регулярної множини існує регулярна граматика, яка її породжує. Нехай M  недетермінований скінченний автомат, який розпізнає цю множину (він існує за теоремою 38.2). Можна вважати, що в ньому немає переходу в початковий стан s₀. Побудуємо регулярну граматику G = (V, T, S, P). Кожний символ алфавіту V в граматиці G вводимо відповідно до символу стану чи вхідного символу автомата M. Множина T термінальних символів граматики G якраз і відповідає символам вхідного алфавіту I автомата M, а початковий символ S граматики G  символу початкового стану s₀ автомата M.

---

Множину P продукцій граматики G сформуємо на основі переходів у автоматі M. Якщо стан s у разі вхідного символу a переходить у кінцевий стан, то до множини P додають продукцію A_sa, де A_s  нетермінальний символ граматики G, що відповідає стану s. Якщо стан s переходить у стан t в разі вхідного символу a, то до множини P додають продукцію A_saA_t. Продукцію S додають до P, якщо й тільки якщо L(M). Отже, продукції в граматиці G відповідають переходам в автоматі M. Тепер легко переконатись, що L(G)=L(M). ►

Побудуємо недетермінований скінченний автомат для розпізнавання мови, породженої регулярною граматикою G = (V, T, S, P), де V = {0, 1, A, S}, T = {0, 1}, а множина P складається з таких продукції: S  0S, S  1A, S  1, A  1A, A  1, S  . Діаграму переходів для автомата, який розпізнає мову L(G), зображено на рис. 38.5. Тут s₀ – стан, який відповідає початковому символу S граматики G, s₁ – стан, який відповідає нетерміналу A, s₂ – заключний стан.

Рис. 38.5.

Розглянемо зворотній приклад. На рис. 38.6 зображено діаграму переходів скінченого автомата. Знайдемо регулярну граматику, яка породжує розпізнавану ним регулярну множину.

Граматика G = (V, T, S, P) має алфавіт V = {S, A, B, 0, 1}, T = {0, 1}; нетеремінальні символ S, A та B відповідають станам s₀, s₁ та s₂ автомата; її початковий символ – S, а продукції: S0A, S1B, S1, S, A0A, A1B, A1, B0A, B1B та B1. Усі ці продукції отримано так, як це описано в другій частині доведення теореми 38.3.

Рис. 38.6.

Із теорем 38.2 та 38.3 безпосередньо випливає таке твердження.

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

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

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

---

Смотрите также файлы

• dinamika.docx

• dinamika_1.docx

• komivoyazhera.docx

• Lektsiya8.doc

• M51_21_-_kopia.pdf