Omdannelse af automat til regulært udtryk

Vi viser, hvordan man omdanner en vilkårlig endelig automat til et regulært udtryk.

Beskrivelse af algoritmen

Som input har vi en NFA A. Først gør vi den til en GNFA. I anden fase fjerner vi i hvert trin én tilstand, ændrer overgangsfunktionen korrekt og gentager, indtil der kun er to tilstande tilbage — start- og accepttilstanden. Mellem dem går der en kant, som har et regulært udtryk som mærkat, og det er resultatet af hele algoritmen. Hele fremgangsmåden består således først og fremmest i at fjerne en tilstand og derefter rette automaten, så vi får en ækvivalent automat.

Fjernelse af én tilstand

Hvordan man fjerner én tilstand, kan vi illustrere med et enkelt eksempel. Antag, at en del af vores automat ser således ud:

hvor R_i er nogle regulære udtryk. Hvordan ville automaten se ud, hvis vi fjernede tilstanden q_r? Vi kan forestille os, at vi er i tilstanden q_i og spørger, hvilke ord vi kan generere på dette stykke. Hvis vi går direkte fra tilstanden q_i til tilstanden q_j, er det alle de ord, der svarer til det regulære udtryk R₄.

Hvis vi derimod går til tilstanden q_r, kan vi generere ord af formen R₁. I tilstanden q_r kan vi dog køre rundt i løkken for det regulære udtryk R₂, så vi kan faktisk generere ord af formen $R_1\circ (R_2^{\ast })$. Og da vi desuden kan komme fra tilstanden q_r til tilstanden q_j, tilføjer vi her også det regulære udtryk R₃. Alt i alt kan vi ad denne vej få ord af formen $R_1\circ (R_2^{\ast })\circ R_3$.

Nu ved vi, at der fra denne del af automaten kan opstå ord af formen R₄ eller af formen $R_1\circ (R_2^{\ast })\circ R_3$. Det kan vi selvfølgelig skrive som et regulært udtryk således: $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Nu kan vi helt enkelt fjerne tilstanden q_r og lade kun de to tilstande q_i og q_j blive tilbage, og i stedet for R₄ skriver vi det regulære udtryk, vi lige har udregnet:

Denne fremgangsmåde udfører vi med hver kant fra hver tilstand q_i til en tilstand q_j, også løkker, dvs. også tilfældet, hvor q_i = q_j.

Efter fjernelsen af én tilstand får vi en ækvivalent automat — en automat, der genkender det samme sprog.

Hele algoritmen

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

1. Vi omdanner NFA'en A til en GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Herefter betegner vi antallet af tilstande i Z med bogstavet k.
2. Hvis k = 2, slutter algoritmen, og på kanten mellem start- og accepttilstanden står det resulterende regulære udtryk.
3. Hvis k>2, vælger vi en vilkårlig tilstand q_r, som er forskellig fra start- og accepttilstanden, dvs. q_r ≠ q₀′ og q_r ≠ q_f′. Dernæst danner vi en ny GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩, for hvilken der gælder: $$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₀′} lad $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ hvor R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Fortsæt derefter med trin 2.

Eksempel

Lad os tage denne endelige automat som input:

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

Nu anvender vi anden del af algoritmen og fjerner en knude. Vi begynder med knuden q₂. Vi fjerner knuden q₂ og tilføjer en overgang fra tilstanden q₁ til tilstanden q_f. Denne overgang mærker vi b(a|b)^∗, fordi vi fra knuden q₁ kommer til tilstanden q₂ med ord af formen b, derefter kan vi køre rundt i løkken for a|b, og dermed får vi (a|b)^∗, og til sidst går vi via epsilon-reglen videre til q_f. Her gælder, at b(a|b)^∗ϵ = b(a|b)^∗. Vi får automaten:

Tilbage er det at fjerne den sidste tilstand, q₁. Vi tilføjer en kant fra tilstanden q_s til tilstanden q_f. Hvordan mærker vi den? Til tilstanden q₁ kommer vi via epsilon-reglen, den kan vi straks udelade. Derefter kan vi køre rundt i løkken for a, så vi får det regulære udtryk a^∗. Og til sidst kommer vi via en kant til q_f, så vi konkatenerer desuden udtrykket med b(a|b)^∗. Kanten mærker vi altså med det regulære udtryk a^∗b(a|b)^∗.

Automaten har nu kun to tilstande, så algoritmen slutter. På kanten står det resulterende regulære udtryk.

Kilder

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