Automata átalakítása reguláris kifejezéssé

Megmutatjuk, hogyan alakíthatunk át tetszőleges véges automatát reguláris kifejezéssé.

Az algoritmus leírása

A bemeneten van egy NVA-nk, jelöljük A-val. Először belőle ÁNVA-t csinálunk. A második fázisban minden lépésben elhagyunk egy állapotot, megfelelően módosítjuk az átmeneti függvényt, és ezt addig ismételjük, amíg csak két állapot marad – a kezdő- és a végállapot. Köztük egy él fut, amelynek a címkéje egy reguláris kifejezés, és ez lesz az egész algoritmus eredménye. Az egész eljárás tehát főként egy állapot elhagyásából áll, majd az automata olyan kijavításából, hogy ekvivalens automatát kapjunk.

Egy állapot elhagyása

Hogyan hagyunk el egy állapotot, azt egy egyszerű példán szemléltethetjük. Tegyük fel, hogy az automatánk egy része így néz ki:

ahol az R_i valamilyen reguláris kifejezések. Hogyan nézne ki az automata, ha elhagynánk a q_r állapotot? Képzeljük el, hogy a q_i állapotban vagyunk, és azt kérdezzük: milyen szavakat tudunk előállítani ezen a szakaszon? Ha a q_i állapotból egyenesen a q_j állapotba megyünk, akkor ezek mind az R₄ reguláris kifejezésnek megfelelő szavak.

Ha viszont a q_r állapotba megyünk, akkor R₁ alakú szavakat állíthatunk elő. A q_r állapotban azonban az R₂ reguláris kifejezés szerint körözhetünk is, vagyis tulajdonképpen $R_1\circ (R_2^{\ast })$ alakú szavakat állíthatunk elő. És mivel a q_r állapotból még el is juthatunk a q_j állapotba, ehhez hozzávesszük az R₃ reguláris kifejezést is. Ezen az úton tehát összesen $R_1\circ (R_2^{\ast })\circ R_3$ alakú szavakat kaphatunk.

Most már tudjuk, hogy az automata ezen részéből R₄ alakú vagy $R_1\circ (R_2^{\ast })\circ R_3$ alakú szavak keletkezhetnek. Ezt természetesen felírhatjuk reguláris kifejezésként is: $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Most már egyszerűen elhagyhatjuk a q_r állapotot, csak a q_i és a q_j állapot marad, és az R₄ helyére éppen a kiszámított reguláris kifejezést írjuk:

Ezt az eljárást elvégezzük minden q_i állapotból minden q_j állapotba vezető éllel, a hurkokat is beleértve, vagyis azt az esetet is, amikor q_i = q_j.

Egy állapot elhagyása után ekvivalens automatát kapunk – olyan automatát, amely ugyanazt a nyelvet ismeri fel.

A teljes algoritmus

A bemeneten van egy NVA: A = ⟨Q, Σ, δ, q₀, F⟩.

1. Az A NVA-t átalakítjuk a Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩ ÁNVA-vá. A továbbiakban k jelöli a Z állapotainak számát.
2. Ha k = 2, az algoritmus véget ér, és a kezdő- és a végállapot közötti élen van a végeredményül kapott reguláris kifejezés.
3. Ha k>2, választunk egy tetszőleges q_r állapotot, amely különbözik a kezdő- és a végállapottól, azaz q_r ≠ q₀′ és q_r ≠ q_f′. Ezután létrehozunk egy új Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ ÁNVA-t, amelyre igaz: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ és minden q_i ∈ Q′′ ∖ {q_f′} és minden q_j ∈ Q′′ ∖ {q₀′} esetén legyen $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ ahol R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Ezután folytasd a 2. lépéssel.

Példa

Legyen a bemeneten ez a véges automata:

Először átalakítjuk ÁNVA-vá (a felesleges ∅-átmeneteket nem ábrázoljuk):

Most alkalmazzuk az algoritmus második részét, és elhagyunk valamelyik csúcsot. Kezdjük a q₂ csúccsal. Elhagyjuk a q₂ csúcsot, és felveszünk egy átmenetet a q₁ állapotból a q_f állapotba. Ezt az átmenetet b(a|b)^∗-gal címkézzük, mert a q₁ csúcsból a q₂ állapotba b alakú szavakkal jutunk, ott aztán az a|b szerint körözhetünk, így megkapjuk az (a|b)^∗ kifejezést, végül az epszilon-átmenettel átlépünk a q_f állapotba. Közben igaz, hogy b(a|b)^∗ϵ = b(a|b)^∗. Ezt az automatát kapjuk:

Már csak az utolsó állapotot kell elhagynunk, a q₁-et. Felveszünk egy élt a q_s állapotból a q_f állapotba. Mivel címkézzük? A q₁ állapotba epszilon-átmenettel jutunk, ezt rögtön elhagyhatjuk. Aztán körözhetünk az a szerint, így megkapjuk az a^∗ reguláris kifejezést. Végül az élen át eljutunk a q_f állapotba, vagyis a kifejezést még összefűzzük a b(a|b)^∗ kifejezéssel. Az élt tehát az a^∗ b(a|b)^∗ reguláris kifejezéssel címkézzük.

Az automatának már csak két állapota van, tehát az algoritmus véget ér. Az élen van a végeredményül kapott reguláris kifejezés.

Források

• A példa és az algoritmus leírása innen származik: M. Sipser: Introduction to the Theory of Computation