Omforming av automat til regulært uttrykk

Vi skal vise hvordan du omformer en vilkårlig endelig automat til et regulært uttrykk.

Beskrivelse av algoritmen

Som input har vi en NFA A. Først gjør vi den om til en GNFA. I den andre fasen fjerner vi i hvert steg én tilstand, endrer overgangsfunksjonen riktig og gjentar dette til det bare er to tilstander igjen — start- og sluttilstanden. Mellom dem går det en kant som har et regulært uttrykk som merke, og dette uttrykket blir resultatet av hele algoritmen. Hele framgangsmåten består altså først og fremst i å fjerne en tilstand og deretter rette opp automaten slik at vi får en ekvivalent automat.

Eliminering av én tilstand

Hvordan vi fjerner én tilstand, kan vi vise på et enkelt eksempel. Anta at en del av automaten vår ser slik ut:

der R_i er noen regulære uttrykk. Hvordan ville automaten sett ut hvis vi fjernet tilstanden q_r? Vi kan tenke oss at vi er i tilstanden q_i og spør hvilke ord vi kan generere på denne strekningen. Hvis vi går fra tilstanden q_i direkte til tilstanden q_j, blir det alle ord som svarer til det regulære uttrykket R₄.

Hvis vi derimot går til tilstanden q_r, kan vi generere ord på formen R₁. I tilstanden q_r kan vi imidlertid gå i løkke for det regulære uttrykket R₂, så vi kan egentlig generere ord på formen $R_1\circ (R_2^{\ast })$. Og siden vi dessuten kan komme fra tilstanden q_r til tilstanden q_j, legger vi til det regulære uttrykket R₃ også. Totalt kan vi altså på denne veien få ord på formen $R_1\circ (R_2^{\ast })\circ R_3$.

Nå vet vi at det fra denne delen av automaten kan oppstå ord på formen R₄ eller på formen $R_1\circ (R_2^{\ast })\circ R_3$. Det kan vi selvfølgelig skrive som et regulært uttrykk: $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Nå kan vi enkelt fjerne tilstanden q_r og la bare de to tilstandene q_i og q_j bli igjen, og i stedet for R₄ skriver vi det regulære uttrykket vi nettopp regnet ut:

Denne framgangsmåten utfører vi med hver kant fra hver tilstand q_i til en tilstand q_j, inkludert løkker, altså også tilfellet der q_i = q_j.

Etter at vi har fjernet én tilstand, får vi en ekvivalent automat — en automat som gjenkjenner det samme språket.

Hele algoritmen

Som input har vi en NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Vi omformer NFA-en A til en GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Videre betegner vi antallet tilstander i Z med bokstaven k.
2. Hvis k = 2, stopper algoritmen, og på kanten mellom start- og sluttilstanden står det resulterende regulære uttrykket.
3. Hvis k>2, velger vi en vilkårlig tilstand q_r som er forskjellig fra start- og sluttilstanden, altså q_r ≠ q₀′ og q_r ≠ q_f′. Videre lager vi en ny GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ som oppfyller: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ og for alle q_i ∈ Q′′ ∖ {q_f′} og for alle q_j ∈ Q′′ ∖ {q₀′} la $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ der R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Fortsett videre med steg 2.

Eksempel

La oss ha denne endelige automaten som input:

Først omformer vi den til en GNFA (unødvendige ∅-overganger tegner vi ikke):

Nå bruker vi den andre delen av algoritmen og fjerner en node. Vi begynner med noden q₂. Vi fjerner noden q₂ og legger til en overgang fra tilstanden q₁ til tilstanden q_f. Denne overgangen merker vi b(a|b)^∗, for fra noden q₁ kommer vi til tilstanden q₂ for ord på formen b, så kan vi gå i løkke for a|b, og slik får vi (a|b)^∗, og til slutt går vi med epsilonregelen over til q_f. Her gjelder b(a|b)^∗ϵ = b(a|b)^∗. Vi får automaten:

Det gjenstår å fjerne den siste tilstanden, q₁. Vi legger til en kant fra tilstanden q_s til tilstanden q_f. Hvordan merker vi den? Til tilstanden q₁ kommer vi med epsilonregelen, den kan vi bare utelate. Så kan vi gå i løkke for a, og da får vi det regulære uttrykket a^∗. Og til slutt kommer vi via kanten til q_f, så uttrykket konkatenerer vi i tillegg med b(a|b)^∗. Kanten merker vi altså med det regulære uttrykket a^∗ b(a|b)^∗.

Automaten har nå bare to tilstander, så algoritmen stopper. På kanten står det resulterende regulære uttrykket.

Kilder

• Eksempelet og beskrivelsen av algoritmen stammer fra M. Sipser: Introduction to the Theory of Computation