Регулярні вирази Основні визначення регулярні вирази ст. Перетворення ДКА на НКА

ДКА є окремим випадком НКА. В ньому:

немає стану з ε-переходами;

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

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

На малюнку 3 показаний граф переходів ДКА, що допускає ту ж мову (a|b) * a(a|b)(a|b), що і НКА на малюнку 1.

Малюнок 3. ДКА, що допускає рядок (a | b) * a (a | b) (a | b).

Детермінований кінцевий автомат M, який допускає цю мову:

M = ((1, 2, 3, 4, 5, 6, 7, 8), (a, b), D, 1, (3, 5, 6, 8))

Функція переходів D визначається так:

Побудова НК за регулярним виразом

1. Для ε НКА має такий вигляд (0 – початковий стан, 1 – кінцевий):

2. Для а, що входить до цієї мови НКА:

3. Нехай N(s) та N(t) – НКА для регулярних виразів s та t.

Для регулярного виразу s|t складової НКА має такий вигляд:

b. Для регулярного вираження st НКА:

с. Для вираження s* НКА має вигляд:

d. Для вираження у дужках (s) використовується НКА N(s) як у пункті а.

Кожен новий стан отримує індивідуальне ім'я. Побудова НКА N(r) має такі характеристики:

N(r) має кількість станів, яка не перевищує кількості символів більш ніж 2 рази.

N(r) має рівно один початковий і один кінцевий стан. Кінцевий стан немає вихідних переходів.

Кожен стан N(r) має або 1 перехід для символу з алфавіту (), або не більше 2 вихідних ε-переходів.

Перетворення нка в дка.

НКА на малюнку 1 має 2 переходи зі стану 0 символу а: стану 0 і 1. Такий перехід неоднозначний, як і перехід по ε. Моделювання таких НКА за допомогою комп'ютерної програми значно утруднюється. Визначення допустимості стверджує, що має існувати певний шлях з початкового стану до кінцевого, але коли є кілька шляхів для одного і того ж вхідного рядка, їх треба розглядати все, щоб знайти шлях до заключного стану або з'ясувати, що такого шляху немає.

У таблиці переходів НКА кожного запису відповідає безліч станів, а таблиці переходів ДКА – лише одне. Суть перетворення у тому, кожен стан ДКА відповідає безлічі станів НКА. ДКА використовує свої стани для відстеження всіх можливих станів, у яких НКА може бути після читання чергового вхідного символу. Тобто після читання вхідного потоку ДКА знаходиться в стані, який представляє деяку кількість станів НКА, досяжних з початкового шляху, що відповідає вхідному рядку. Кількість таких станів ДКА може значно перевищувати кількість станів НКА (експоненційна залежність), але на практиці це зустрічається вкрай рідко, а часом у ДКА навіть менше станів, ніж у НКА.

Розглянемо подібне перетворення на конкретному прикладі. На малюнку 4 зображено ще один НКА, який допускає мову (a|b) * a(a|b)(a|b) (як і на рисунках 1 та 3).

Малюнок 4. НКА, що допускає мову (a|b) * a(a|b)(a|b)

Зображений на малюнку перехід зі стану 13 стан 14 може бути представлений аналогічно переходу з 8-го в 13-е стан.

Побудуємо ДКА для цієї мови. Стартовий стан еквівалентного ДКА являє собою стан A = (0, 1, 2, 4, 7), тобто стани, в які можна потрапити з 0 по ε.

Алфавіт вхідних символів є (a, b). З початкового стану А можна обчислити стан, досяжний за а. Назвемо цей стан У = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14).

Серед станів А тільки стан 4 має перехід по b в стан 5, так що ДКА має перехід по b з А в стан С = (1, 2, 4, 5, 6, 7).

Якщо продовжити цей процес зі станами В і С, всі множини станів НКА будуть позначені. Таким чином будемо мати безліч станів:

A = (0, 1, 2, 4, 7)

В = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)

С = (1, 2, 4, 5, 6, 7)

D = (10, 12, 13, 14)

Стан А – початковий, а стани B, D, E – заключні.

Повністю таблицю переходів наведено нижче.

Нижче на малюнку 5 наведено сам ДКА для цієї мови.

Малюнок 5. ДКА, що допускає мову (a|b) * a(a|b)(a|b)

Список використаної литературы:

Пентус А. Є., Пентус М. Р. - Теорія формальних мов

А. Ахо, Р. Мережі, Д, Ульман - Компілятори: принципи, технології, інструменти.

Регулярні вирази

Регулярні вирази (РВ) - це дуже зручна форма запису про регулярних або автоматних мов. Тому РВ використовуються як вхідна мова в багатьох системах, що обробляють ланцюжки. Розглянемо приклади таких систем:

Команда grep операційної системи Unix або аналогічні команди для пошуку ланцюжків, які можна зустріти у Web-броузерах або системах форматування тексту. У таких системах РВ використовуються для опису шаблонів, які шукає користувач у файлі. Різні пошукові системи перетворюють РВ або детермінований кінцевий автомат (ДКА), або недетермінований кінцевий автомат (НКА) і застосовують цей автомат до файлу, в якому проводиться пошук.
Генератори лексичних аналізаторів Лексичні аналізатори є компонентом компілятора, вони розбивають вихідну програму на логічні одиниці (лексеми), які можуть опинитися складатися з однієї чи кількох символів і мають певний сенс. Генератор лексичних аналізаторів отримує формальні описи лексем, що є по суті РВ, і створює ДКА, який розпізнає, яка з лексем з'являється на його вході.
РВ у мовах програмування.

У цій статті ми спочатку ознайомимося з кінцевими автоматами та їх видами (ДКА та НКА), і далі розглянемо приклад побудови мінімального ДКА за регулярним виразом.

Кінцеві автомати

Кінцевий автомат (КА) - це перетворювач, який дозволяє зіставити входу відповідний вихід, причому цей вихід може залежати не тільки від поточного входу, але і від того, що відбувалося раніше, від передісторії роботи кінцевого автомата. Навіть поведінку людини, а не лише штучних систем можна описати за допомогою КА. Наприклад, ваша реакція на те, що ваш сусід слухає голосно музику ночами, буде однією після першого такого випадку і зовсім іншою після кількох таких випадків. Таких передісторій може бути нескінченне число, виникає питання: якою пам'яттю повинен мати КА, щоб поводитися по-різному для кожної передістрої? Зрозуміло, що зберігати нескінченну кількість передісторій неможливо. Тому автомат хіба що розбиває всі можливі передісторії на класи еквівалентності. Дві історії є еквівалентними, якщо вони однаково впливають на поведінку автомата надалі. Клас еквівалентності якого автомат відніс свою поточну передісторію, називають ще внутрішнім станом автомата.

Розглянемо приклад роботи примітивного КА:

Даний КА складається з:

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

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

Тепер розглянемо, як можна задати КА. Вони можуть задаватися у вигляді графів або у вигляді таблиць, що управляють. У вигляді графа КА задається в такий спосіб:

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

У вигляді таблиці, що управляє, так:

стани КА розташовуються у рядках таблиці.
символи розпізнаваної мови – у стовпцях.
на перетині вказується стан, у який можна потрапити з даного стану за цим символом.

Приклад КА у вигляді графа і у вигляді таблиці, що управляє, буде представлений нижче.

ДКА та НКА

Основна відмінність ДКА і НКА у тому, що ДКА у процесі роботи може лише в одному стані, а НКА у кількох станах одночасно. Як приклад роботи НКА можна навести ідею американського фізика Х'ю Еверетта від того, що будь-яка подія розбиває світ на кілька світів, у кожному з яких ця подія закінчилася по-своєму. Наприклад, в одному світі Гітлер виграв Другу світову війну, в іншому - Ньютон замість фізики зайнявся бізнесом і відкриття законів класичної механіки довелося відкласти років на 50. Щоб зробити якісь висновки з роботи автомата, слід вивчити всі світи. Після того, як весь вхідний ланцюжок буде рахований, ми вважаємо, що НКА допускає цей ланцюжок, якщо він завершив роботу в припустимому стані хоча б в одному з безлічі «світів». Відповідно, автомат відкидає ланцюжок, якщо він завершив роботу в недопущеному стані у кожному «світі». ДКА ж приймає ланцюжок, це очевидно, якщо після зчитування всього вхідного ланцюжка він виявляється в стані, що допускає.

Найчастіше побудувати НКА набагато простіше ніж ДКА. Але, незважаючи на це використовувати НКА для моделювання - не найкраща ідея. На щастя, для кожного НКА можна побудувати ДКА, що допускає ту саму вхідну мову. У цій статті ми не наводитимемо алгоритм побудови ДКА по НКА, а розглянемо даний алгоритм на основі наочного прикладу нижче.

Побудова мінімального ДКА за регулярним виразом

Для початку наведемо список операцій РВ, що використовується в даній статті, в порядку їх пріоритетності:

ітерація (замикання Клині) за допомогою символу "*"
конкатенація задається за допомогою пробілу або порожнього рядка (наприклад: ab)
об'єднання за допомогою символу "|"

Розглянемо приклад, дано регулярне вираз:

Xy* (x | y*) | ab (x | y *) | (x | a *) (x | y *)

Потрібно побудувати мінімальний ДКА за регулярним виразом і продемонструвати розпізнавання коректного та некоректного ланцюжка.

Для початку спростимо цей РВ, використовуючи правосторонній дистрибутивний закон конкатенації щодо об'єднання отримуємо наступне РВ:

(xy * | ab | (x | a *)) (x | y *)

Тепер будуємо автомат за цим РВ:

За правилом перетворення конкатенації (не наводитимемо правила перетворення РВ в КА, оскільки вони досить очевидні), отримуємо наступний автомат:

За правилом перетворення об'єднання:

За правилом перетворення конкатенації:

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

Позбавляємося ε-переходів («зірочкою» позначені кінцеві стани):

У даному НКА стану s3 і s5 еквівалентні, так як δ(s3, x) = δ(s5, x) = s1 та δ(s3, y) = δ(s5, y) = s5, s7. Перейменовуємо стани s6 -> s5 і s7 -> s6:

Будуємо ДКА з НКА:

У цьому ДКА стану p1 і p5 еквівалентні, оскільки
δ(p1, x) = δ(p5, x) = p4 і δ(p1, y) = δ(p5, y) = p5. Перейменовуємо стани p6 -> p5 і p7 -> p6:

Цей автомат є мінімальним ДКА.

Нехай δ - функція переходів, то розширену функцію переходів, побудовану δ, позначимо δ', і ω - вхідний ланцюжок.

Допустимо на вхід подається ланцюжок ω = aaax, ми очікуємо, що автомат опиниться в одному з станів, що допускають.

δ(p0, ε) = p0
δ(p0, a) = δ(δ'(p0, ε), a) = δ(p0, a) = p3
δ(p0, aa) = δ(δ'(p0, a), a) = δ(p3, a) = p5
δ(p0, aaa) = δ(δ'(p0, aa), a) = δ(p5, a) = p5
δ(p0, aaax) = δ(δ'(p0, aaa), x) = δ(p5, x) = p4

P4 - допустимий кінцевий стан, таким чином ланцюжок aaax є коректним для даного автомата.

Тепер припустимо, що ω = xyyb:

δ(p0, ε) = p0
δ(p0, x) = δ(δ'(p0, ε), x) = δ(p0, x) = p1
δ'(p0, xy) = δ(δ'(p0, x), y) = δ(p1, y) = p1
δ(p0, xyy) = δ(δ'(p0, xy), y) = δ(p1, y) = p1
δ(p0, xyyb) = δ(δ'(p0, xyy), b) = δ(p1, b) = ∅

Тут бачимо, що й подати на вхід автомату символ b, що він перебуває у стані p1, цей автомат помре, отже ланцюжок xyyb - некоректна.

PS У даній статті було розглянуто алгоритм побудова ДКА по РВ, але існують зручніші алгоритми, зокрема для програмування, але це вже тема для іншої статті…

Команда grep операційної системи Unix або аналогічні команди для пошуку ланцюжків, які можна зустріти у Web-броузерах або системах форматування тексту. У таких системах РВ використовуються для опису шаблонів, які шукає користувач у файлі. Різні пошукові системи перетворюють РВ або детермінований кінцевий автомат (ДКА), або недетермінований кінцевий автомат (НКА) і застосовують цей автомат до файлу, в якому проводиться пошук.
Генератори лексичних аналізаторів Лексичні аналізатори є компонентом компілятора, вони розбивають вихідну програму на логічні одиниці (лексеми), які можуть опинитися складатися з однієї чи кількох символів і мають певний сенс. Генератор лексичних аналізаторів отримує формальні описи лексем, що є по суті РВ, і створює ДКА, який розпізнає, яка з лексем з'являється на його вході.
РВ у мовах програмування.

Кінцеві автомати

Кінцевий автомат (КА) - це перетворювач, який дозволяє зіставити входу відповідний вихід, причому цей вихід може залежати не тільки від поточного входу, але і від того, що відбувалося раніше, від передісторії роботи кінцевого автомата. Навіть поведінку людини, а не лише штучних систем можна описати за допомогою КА. З допомогою КА можна описати як поведінка штучних систем, і навіть поведінка людини. Наприклад, ваша реакція, на те, що ваш сусід слухає голосно музику ночами, буде однією після першого такого випадку і зовсім іншою після кількох таких випадків. Таких передісторій може бути нескінченна кількість, виникає питання; Якою пам'яттю має володіти КА, щоб поводитися по-різному для кожної передустрою? Зрозуміло, що зберігати нескінченну кількість передісторій неможливо. Тому автомат хіба що розбиває всі можливі передісторії на класи еквівалентності. Дві історії є еквівалентними, якщо вони однаково впливають на поведінку автомата надалі. Клас еквівалентності якого автомат відніс свою поточну передісторію, називають ще внутрішнім станом автомата.

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

У вигляді таблиці, що управляє, так:

стани КА розташовуються у рядках таблиці.
символи розпізнаваної мови – у стовпцях.
на перетині вказується стан, у який можна потрапити з даного стану за цим символом.

Приклад КА у вигляді графа і у вигляді таблиці, що управляє, буде представлений нижче.

ДКА та НКА

Основна відмінність ДКА і НКА у тому, що ДКА у процесі роботи може лише в одному стані, а НКА у кількох станах одночасно. Як приклад роботи НКА можна навести ідею американського фізика Х'ю Еверетта від того, що будь-яка подія розбиває світ на кілька світів, у кожному з яких ця подія закінчилася по-своєму. Наприклад, у світі Гітлер виграв 2-ю Мир. війну, в іншому – Ньютон замість фізики зайнявся бізнесом і відкриття законів класичної механіки довелося відкласти на 50 років. Щоб зробити якісь висновки з роботи автомата, слід вивчити всі «світи». Після того, як весь вхідний ланцюжок буде рахований, ми вважаємо, що НКА допускає цей ланцюжок, якщо він завершив роботу в припустимому стані хоча б в одному з безлічі «світів». Відповідно, автомат відкидає ланцюжок, якщо він завершив роботу в недопущеному стані у кожному «світі». ДКА ж приймає ланцюжок, це очевидно, якщо після зчитування всього вхідного ланцюжка він виявляється в стані, що допускає.

Побудова мінімального ДКА за регулярним виразом

Для початку наведемо синтаксис РВ, що використовується в даній статті:

конкатенація задається за допомогою пробілу або порожнього рядка (наприклад: ab)
об'єднання за допомогою символу "|"
ітерація(замикання Клині), за допомогою символу "*"

Розглянемо приклад, дано регулярне вираз:

xy* (x|y*) | ab (x | y *) | (x | a *) (x | y *)

(xy * | ab | (x | a *)) (x | y *)

Тепер будуємо автомат за цим РВ:

За правилом перетворення об'єднання:

За правилом перетворення конкатенації:

І наприкінці застосовуємо правило перетворення замикання та отримуємо εНКА:

Позбавляємося ε-переходів («зірочкою» позначені кінцеві стани):

Будуємо ДКА з НКА:

Цей автомат є мінімальним ДКА.

Нехай δ - функція переходів, то розширена функція переходів, побудовану δ, позначимо δ', і ω - вхідний ланцюжок.

Допустимо на вхід подається ланцюжок ω = aaax, ми очікуємо що автомат опиниться в одному з станів, що допускають.

δ(p0, ε) = p0
δ(p0, a) = δ(δ'(p0, ε), a) = δ(p0, a) = p3
δ(p0, aa) = δ(δ'(p0, a), a) = δ(p3, a) = p5
δ(p0, aaa) = δ(δ'(p0, aa), a) = δ(p5, a) = p5
δ(p0, aaax) = δ(δ'(p0, aaa), a) = δ(p5, a) = p4

p4 - допустимий кінцевий стан, таким чином ланцюжок aaax, є коректним для даного автомата.

Тепер припустимо, що ω = xyyb:

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

Алгоритм 3.1. Побудова недетермінованого кінцевого автомата за регулярним виразом.

Вхід. Регулярний вираз r в алфавіті T .

Вихід. НКА M , такий, що L(M) = L(r) .

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

Побудова детермінованого кінцевого автомата за недетермінованим

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

Алгоритм 3.2. Побудова детермінованого кінцевого автомата з недетермінованого.

Вхід. НКА M = (Q, T, D, q 0, F).

Вихід. ДКА.

Метод. Кожен стан результуючого ДКА - це кілька станів вихідного НКА.

В алгоритмі будуть використовуватися наступні функції: - безліч станів НКА, досяжних зі станів, що входять до R через тільки переходи по e , тобто безліч

Безліч станів НКА, які є перехід на вході a для станів з R , тобто безліч

Спочатку Q" та D" порожні. Виконати кроки 1-4:

(1) Визначити .

(2) Додати в Q" як непомічений стан

(3) Виконати таку процедуру:

(4) Визначити .

Приклад 3.6. Результат застосування алгоритму 3.2 наведено на рис.

3.10.

Мал. 3.10.

Побудова детермінованого кінцевого автомата за регулярним виразом

Нехай дано регулярний вираз r в алфавіті T . До регулярного виразу r додамо маркер кінця: (r) # . Таке регулярне вираз називатимемо поповненим. У процесі роботи алгоритм використовуватиме поповнене регулярне вираз.

Алгоритм оперуватиме з синтаксичним деревом для поповненого регулярного виразу (r)#, кожен лист якого позначений символом , а кожна внутрішня вершинапозначена знаком однієї з операцій: (конкатенація), |

(Об'єднання), * (Ітерація).

Кожному листу дерева (крім e-листя) надамо унікальний номер, званий позицією, і будемо використовувати його, з одного боку, для посилання на лист у дереві, і, з іншого боку, для посилання на символ, що відповідає цьому листу. Зауважимо, якщо певний символ використовується в регулярному вираженні кілька разів, він має кілька позицій.

Обійдемо дерево T знизу-вгору зліва-направо і обчислимо чотири функції: nullable, firstpos, lastpos і followpos. Три перші функції - nullable, firstpos і lastpos - визначені на вузлах дерева, а followpos - на безлічі позицій. Значенням всіх функцій, крім nullable, є безліч позицій. Функція followpos обчислюється через три інші функції.

Знайти

Побудова детермінованого кінцевого автомата за регулярним виразом

Наведемо тепер алгоритм побудови за регулярним виразом детермінованого кінцевого автомата, що допускає ту ж мову [?].

Нехай дано регулярне вираз r в алфавіті T. До регулярного виразу r додамо маркер кінця: (r) #. Таке регулярне вираз називатимемо поповненим. У процесі роботи алгоритм використовуватиме поповнене регулярне вираз. внутрішня вершинаАлгоритм оперуватиме з синтаксичним деревом для поповненого регулярного виразу (r)#, кожен лист якого позначений символом , а кожна

Функція firstpos(n) для кожного вузла n синтаксичного дерева регулярного виразу дає безліч позицій, які відповідають першим символам підчіпках, що генеруються подвиражением з вершиною в n. Аналогічно, lastpos(n) дає безліч позицій, яким відповідають останні символи підчіпках, що генеруються підвиразами з вершиною n. Для вузла n, поддеревья якого (тобто дерева, які мають вузол n є коренем) можуть породити порожнє слово, визначимоnullable(n)=true, а інших вузлів nullable(n)=false.

Таблиця для обчислення функцій nullable, firstpos та lastpos наведена на рис. 3.11.

Приклад 3.7. На рис. 3.12 наведено синтаксичне дерево для поповненого регулярного виразу (a|b) * abb# з результатом обчислення функцій firstpos і lastpos. Зліва від кожного вузла розташоване значення першоїпози, праворуч від вузла - значенняостанньоїпози. Зауважимо, що ці функції можуть бути обчислені за один обхід дерева.

Якщо i - позиція, то followpos(i) є безліч позицій j таких, що існує деякий рядок... cd ..., що входить у мову, що описується регулярним виразом, така, що позиція i відповідає цьому входженню c, а позиція j - входженнюd.

Мал. 3.11.

Мал. 3.12.

Функція followpos може бути обчислена також за один обхід дерева знизу вгору за такими двома правилами.

1. Нехай n – внутрішній вузол з операцією (конкатенація), u та v – його нащадки. Тоді для кожної позиції i, що входить вlastpos(u), додаємо до безлічі значень followpos(i) безліч firstpos(v).

2. Нехай n – внутрішній вузол з операцією * (ітерація), u – його нащадок. Тоді для кожної позиції i, що входить вlastpos(u), додаємо до безлічі значень followpos(i) безліч firstpos(u).

Приклад 3.8. Результат обчислення функції followpos для регулярного виразу з попереднього прикладу наведено на рис. 3.13.

Алгоритм 3.3. Пряма побудова ДКА за регулярним виразом.

Вхід. Регулярний вираз r в алфавіті T.

Вихід. ДКА M = (Q, T, D, q 0 F), такий що L(M) = L(r).

Метод. Стани ДКА відповідають безлічі позицій.

Спочатку Q і D порожні. Виконати кроки 1-6:

(1) Побудувати синтаксичне дерево для поповненого регулярного виразу (r) #.