Omvandling av automat till reguljärt uttryck

Vi ska se hur man omvandlar vilken som helst ändlig automat till ett reguljärt uttryck.

Beskrivning av algoritmen

Vi utgår från någon NFA A. Först gör vi om den till en GNFA. I den andra fasen tar vi bort ett tillstånd i varje steg, ändrar övergångsfunktionen på rätt sätt och upprepar tills det bara finns två tillstånd kvar, starttillståndet och sluttillståndet. Mellan dem går en båge som har ett reguljärt uttryck som etikett, och det uttrycket är resultatet av hela algoritmen. Hela metoden går alltså främst ut på att ta bort ett tillstånd och sedan rätta automaten så att vi får en ekvivalent automat.

Eliminering av ett tillstånd

Hur man tar bort ett tillstånd kan vi visa med ett enkelt exempel. Anta att en del av vår automat ser ut så här:

där R_i är några reguljära uttryck. Hur skulle automaten se ut om vi tog bort tillståndet q_r? Vi kan tänka oss att vi befinner oss i tillståndet q_i och frågar oss vilka ord vi kan generera på den här sträckan. Om vi går direkt från q_i till q_j är det alla ord som motsvarar det reguljära uttrycket R₄.

Om vi i stället går till tillståndet q_r kan vi generera ord av formen R₁. I tillståndet q_r kan vi dessutom gå runt i en loop med uttrycket R₂, så vi kan generera ord av formen $R_1\circ (R_2^{\ast })$. Eftersom vi sedan också kan ta oss från q_r till q_j lägger vi till det reguljära uttrycket R₃. Totalt kan vi alltså på den här vägen få ord av formen $R_1\circ (R_2^{\ast })\circ R_3$.

Nu vet vi att den här delen av automaten kan ge ord av formen R₄ eller av formen $R_1\circ (R_2^{\ast })\circ R_3$. Det kan vi förstås skriva som ett reguljärt uttryck: $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Nu kan vi enkelt ta bort tillståndet q_r och bara behålla de två tillstånden q_i och q_j, och i stället för R₄ skriver vi det uttryck vi just räknade ut:

Den här proceduren utför vi för varje båge från varje tillstånd q_i till något tillstånd q_j, också för loopar, dvs. även när q_i = q_j.

Efter att ha tagit bort ett tillstånd får vi en ekvivalent automat, alltså en automat som känner igen samma språk.

Hela algoritmen

Vi utgår från en NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Vi omvandlar NFA:n A till en GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Fortsättningsvis betecknar vi antalet tillstånd i Z med bokstaven k.
2. Om k = 2 avslutas algoritmen, och på bågen mellan starttillståndet och sluttillståndet står det resulterande reguljära uttrycket.
3. Om k>2 väljer vi ett godtyckligt tillstånd q_r som skiljer sig från start- och sluttillståndet, dvs. q_r ≠ q₀′ och q_r ≠ q_f′. Därefter skapar vi en ny GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ som uppfyller att $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ och för alla q_i ∈ Q′′ ∖ {q_f′} och alla q_j ∈ Q′′ ∖ {q₀′} låt $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ där R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Fortsätt sedan med steg 2.

Exempel

Vi har den här ändliga automaten:

Först omvandlar vi den till en GNFA (de onödiga ∅-övergångarna ritar vi inte ut):

Nu tillämpar vi den andra delen av algoritmen och tar bort någon nod. Vi börjar med noden q₂. Vi tar bort noden q₂ och lägger till en övergång från tillståndet q₁ till tillståndet q_f. Den märker vi b(a|b)^∗, eftersom vi från noden q₁ kommer till tillståndet q₂ för ord av formen b, sedan kan vi gå runt i en loop med a|b, vilket ger (a|b)^∗, och till sist tar vi oss med epsilonregeln till q_f. Det gäller att b(a|b)^∗ϵ = b(a|b)^∗. Vi får automaten:

Nu återstår att ta bort det sista tillståndet, q₁. Vi lägger till en båge från tillståndet q_s till tillståndet q_f. Hur märker vi den? Till tillståndet q₁ kommer vi via epsilonregeln, och den kan vi direkt utelämna. Sedan kan vi gå runt i en loop med a, så vi får det reguljära uttrycket a^∗. Och till sist kommer vi via bågen till q_f, så vi konkatenerar också uttrycket med b(a|b)^∗. Bågen märker vi alltså med det reguljära uttrycket a^∗ b(a|b)^∗.

Automaten har nu bara två tillstånd, så algoritmen avslutas. På bågen står det resulterande reguljära uttrycket.

Källor

• Exemplet och beskrivningen av algoritmen kommer från M. Sipser: Introduction to the Theory of Computation