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

Ще покажем как да преобразуваме произволен регулярен израз в недетерминиран краен автомат.

Пример

Преди да опишем самия алгоритъм, ще покажем на пример за какво всъщност става дума. Нека имаме този регулярен израз: a(b|c)x^∗. С думи езикът, който регулярният израз поражда, бихме описали като думите, които започват с буквата „a“, следва или буквата „b“, или „c“, и после следва произволен брой букви „x“. Бихме ли могли да построим автомат, който приема този език? Да, виж:

Този автомат очевидно приема същия език. Така възниква въпросът дали за всеки регулярен израз съществува автомат, който приема съответния език. Е, да.

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

Предполагаме, че на входа имаме регулярен израз R. От предишния раздел за регулярните изрази знаем, че регулярният израз може да има общо шест различни вида. Различаваме следователно шест случая:

1. R = a за някакъв символ a ∈ Σ. Т.е. регулярният израз е само един символ от азбуката Σ, над която работим. Автоматът, който би приемал един символ a, би изглеждал така:

   

2. R = ϵ, празната дума. Автоматът, който би приел празната дума, би изглеждал така:

   

3. R = ∅, регулярен израз, който поражда празния език. Автоматът, който би разпознавал такъв език, е този:

   

4. R = R₁ ∪ R₂, където R₁, R₂ са регулярни изрази. Вече знаем, че обединението на регулярни езици е отново регулярен език и че можем да построим автомат, който приема такъв език. С други думи, предполагаме, че имаме автомати, които разпознават езика, породен от изразите R₁ и R₂, и с тяхна помощ построяваме автомат, който приема езика, породен от израза R₁ ∪ R₂. Пример: ако R₁ = a и R₂ = ϵ, по метода получаваме този автомат:

   

5. R = R₁ ∘ R₂, където R₁, R₂ са регулярни изрази. Същият случай като в предишната точка. Конкатенацията на регулярни езици е регулярен език и затова можем да построим автомат, който ще приема такъв език. Така че ако R₁ = a, R₂ = b, конкатенацията би изглеждала така:

   

6. $R=(R_1^{\ast })$, където R₁ е регулярен израз. Отново знаем, че затварянето на регулярен език е регулярен език. Така че ако R = a^∗, автоматът би изглеждал така:

   

С последователно прилагане на тези точки преобразуваме целия регулярен израз в краен автомат.

Цялостен пример

Ще опитаме да преобразуваме регулярния израз (a|bc)^∗. Последователно получаваме тези автомати:

Този получен автомат приема езика, който поражда регулярният израз (a|bc)^∗. Разбира се, автоматът е ужасно сложен и със сигурност съществува много по-прост автомат, който приема същия език. Можем да използваме алгоритъма за преобразуване на НКА в ДКА и след това да извършим минимизиране на автомата.

Източници

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools