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

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

Описание на алгоритъма

На входа имаме някакъв НКА A. Първо от него правим ОНКА. Във втората фаза във всяка стъпка премахваме по едно състояние, променяме правилно преходната функция и повтаряме, докато останат само две състояния — началното и крайното. Между тях ще води ребро, което ще има за етикет регулярен израз, който ще е резултатът от целия алгоритъм. Целият метод следователно се състои най-вече в премахване на състояние и последваща поправка на автомата, така че да получим еквивалентен автомат.

Премахване на едно състояние

Как се премахва едно състояние, можем да покажем на прост пример. Да допуснем, че част от нашия автомат изглежда така:

където R_i са някакви регулярни изрази. Как би изглеждал автоматът, ако премахнем състоянието q_r? Можем да си го представим така, че сме в състоянието q_i и се питаме кои думи можем да породим на този участък. Ако отидем от състоянието q_i директно в състоянието q_j, това ще са всички думи, които отговарят на регулярния израз R₄.

Ако обаче отидем в състоянието q_r, можем да породим думи от вида R₁. В състоянието q_r обаче можем да циклим по регулярния израз R₂, така че всъщност можем да породим думи от вида $R_1\circ (R_2^{\ast })$. И тъй като можем още да стигнем от състоянието q_r до състоянието q_j, добавяме там още регулярния израз R₃. Общо по този път можем да получим думи от вида $R_1\circ (R_2^{\ast })\circ R_3$.

Сега знаем, че от тази част на автомата могат да възникнат думи от вида R₄ или от вида $R_1\circ (R_2^{\ast })\circ R_3$. Това, разбира се, можем да запишем във вид на регулярен израз като $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Сега вече лесно можем да премахнем състоянието q_r и да оставим само двете състояния q_i и q_j, а на мястото на R₄ записваме току-що пресметнатия регулярен израз:

Този метод прилагаме за всяко ребро от всяко състояние q_i към някое състояние q_j, и то включително за примките, т.е. включително случая, когато q_i = q_j.

След премахването на едно състояние получаваме еквивалентен автомат — автомат, който разпознава същия език.

Целият алгоритъм

На входа имаме НКА A = ⟨Q, Σ, δ, q₀, F⟩.

1. Преобразуваме НКА A в ОНКА Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. По-нататък с буквата k ще означаваме броя на състоянията в Z.
2. Ако k = 2, алгоритъмът свършва и на реброто между началното и крайното състояние е полученият регулярен израз.
3. Ако k>2, избираме произволно състояние q_r, което е различно от началното и крайното състояние, т.е. q_r ≠ q₀′ и q_r ≠ q_f′. После създаваме нов ОНКА Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩, за който ще е в сила: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ и за всички q_i ∈ Q′′ ∖ {q_f′} и за всички q_j ∈ Q′′ ∖ {q₀′} нека $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ където R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). После продължи със стъпка 2.

Пример

Нека на входа имаме този краен автомат:

Първо го преобразуваме в ОНКА (излишните ∅-преходи няма да изобразяваме):

Сега прилагаме втората част на алгоритъма и премахваме някой възел. Започваме с възела q₂. Премахваме възела q₂ и добавяме преход от състоянието q₁ към състоянието q_f. Този преход означаваме като b(a|b)^∗, защото от възела q₁ стигаме до състоянието q₂ за думи от вида b, после можем да циклим по a|b, така получаваме (a|b)^∗ и накрая с помощта на ε-правилото преминаваме в q_f. При това b(a|b)^∗ϵ = b(a|b)^∗. Получаваме автомата:

Остава да премахнем последното състояние, q₁. Добавяме ребро от състоянието q_s към състоянието q_f. Как да го означим? До състоянието q₁ стигаме през ε-правилото, което можем веднага да пропуснем. После можем да циклим по a, така че получаваме регулярния израз a^∗. И накрая през реброто стигаме до q_f, така че конкатенираме израза още с b(a|b)^∗. Реброто следователно описваме с регулярния израз a^∗ b(a|b)^∗.

Автоматът вече има само две състояния, така че алгоритъмът свършва. На реброто е полученият регулярен израз.

Източници

• Примерът и описанието на алгоритъма са от M. Sipser: Introduction to the Theory of Computation