✖

Перетворення регулярного виразу на автомат

Kapitoly: Регулярні вирази, Регулярний вираз → автомат, Узагальнений НСА, Автомат → регулярний вираз

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

Приклад

Перш ніж описати сам алгоритм, розглянемо приклад, щоб побачити, чого ми прагнемо. Маємо такий регулярний вираз: $a(b|c)x^\ast$. Словами мову, яку породжує цей регулярний вираз, можна описати так: слова, що починаються буквою «a», далі йде «b» або «c», а потім довільна кількість букв «x». Чи зможемо ми побудувати автомат, який допускає цю мову? Звісно, дивись:

Цей автомат, очевидно, допускає ту саму мову. Виникає запитання, чи для кожного регулярного виразу існує автомат, який допускає відповідну мову. Так, існує.

Опис алгоритму перетворення регулярного виразу на автомат

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

  1. R = a для деякого символу $a\in\Sigma$. Тобто регулярний вираз — це лише один символ алфавіту $\Sigma$, над яким ми працюємо. Автомат, що допускає один символ a, виглядав би так:

  2. R = ε, порожнє слово. Автомат, що допускає порожнє слово, виглядав би так:

  3. R = ∅, регулярний вираз, який породжує порожню мову. Автомат, що розпізнає таку мову, ось такий:

  4. R = R1∪ R2, де R1, R2 — регулярні вирази. Ми вже знаємо, що об'єднання регулярних мов знову є регулярною мовою і що можна побудувати автомат, який допускає таку мову. Іншими словами, припускаємо, що маємо автомати, які розпізнають мови, породжені виразами R1 і R2, і за ними будуємо автомат, що допускає мову, породжену виразом R1∪ R2. Приклад: якщо R1 = a і R2 = ε, то за цим способом отримаємо такий автомат:

  5. $R=R_1\circ R_2$, де R1, R2 — регулярні вирази. Те саме, що в попередньому пункті. Конкатенація регулярних мов є регулярною мовою, тож можна побудувати автомат, який її допускатиме. Отже, якщо R1 = a, R2 = b, то конкатенація виглядала б так:

  6. $R=(R_1^\ast)$, де R1 — регулярний вираз. Знову ж таки, ми знаємо, що замикання Кліні регулярної мови є регулярною мовою. Отже, якщо $R=a^\ast$, то автомат виглядав би так:

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

Повний приклад

Спробуймо перетворити регулярний вираз $(a|bc)^\ast$. Послідовно отримаємо такі автомати:

Отриманий автомат допускає мову, яку породжує регулярний вираз $(a|bc)^\ast$. Звісно, автомат вийшов страшенно складним, і напевно існує набагато простіший автомат, що допускає ту саму мову. Можемо застосувати алгоритм перетворення НСА на ДСА, а потім виконати мінімізацію автомата.

Джерела