Omzetting van een automaat naar een reguliere expressie

We laten zien hoe je een willekeurige eindige automaat omzet naar een reguliere expressie.

Beschrijving van het algoritme

De invoer is een NFA A. Eerst maken we er een GNFA van. In de tweede fase verwijderen we in elke stap één toestand, passen we de overgangsfunctie op de juiste manier aan en herhalen we dat tot er nog maar twee toestanden overblijven — de begin- en de eindtoestand. Daartussen loopt een pijl met als label een reguliere expressie, en die is het resultaat van het hele algoritme. De hele werkwijze bestaat dus vooral uit het verwijderen van een toestand en het daaropvolgend herstellen van de automaat, zodat we een equivalente automaat krijgen.

Het verwijderen van één toestand

Hoe je één toestand verwijdert, kunnen we laten zien aan een eenvoudig voorbeeld. Stel dat een deel van onze automaat er zo uitziet:

waarbij R_i reguliere expressies zijn. Hoe zou de automaat eruitzien als we toestand q_r verwijderden? We kunnen het ons zo voorstellen dat we in toestand q_i zitten en ons afvragen welke woorden we op dit stuk allemaal kunnen genereren. Als we vanuit toestand q_i rechtstreeks naar toestand q_j gaan, zijn dat alle woorden die overeenkomen met de reguliere expressie R₄.

Gaan we echter naar toestand q_r, dan kunnen we woorden van de vorm R₁ genereren. In toestand q_r kunnen we echter rondlopen voor de reguliere expressie R₂, dus eigenlijk kunnen we woorden van de vorm $R_1\circ (R_2^{\ast })$ genereren. En omdat we vanuit toestand q_r nog naar toestand q_j kunnen komen, voegen we daar nog de reguliere expressie R₃ aan toe. In totaal kunnen we via dit pad dus woorden van de vorm $R_1\circ (R_2^{\ast })\circ R_3$ krijgen.

Nu weten we dat uit dit deel van de automaat woorden van de vorm R₄ of van de vorm $R_1\circ (R_2^{\ast })\circ R_3$ kunnen ontstaan. Dat kunnen we natuurlijk als reguliere expressie opschrijven als $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Nu kunnen we toestand q_r eenvoudig verwijderen en alleen de twee toestanden q_i en q_j laten staan, en in plaats van R₄ schrijven we de zojuist berekende reguliere expressie:

Deze werkwijze passen we toe op elke pijl vanuit elke toestand q_i naar een toestand q_j, inclusief lussen, dus ook in het geval dat q_i = q_j.

Na het verwijderen van één toestand krijgen we een equivalente automaat — een automaat die dezelfde taal herkent.

Het hele algoritme

De invoer is een NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. We zetten de NFA A om in een GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Met de letter k geven we hierna het aantal toestanden in Z aan.
2. Als k = 2, stopt het algoritme en staat op de pijl tussen de begin- en de eindtoestand de resulterende reguliere expressie.
3. Als k>2, kiezen we een willekeurige toestand q_r die verschilt van de begin- en de eindtoestand, dus q_r ≠ q₀′ en q_r ≠ q_f′. Vervolgens maken we een nieuwe GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ waarvoor zal gelden: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ en voor alle q_i ∈ Q′′ ∖ {q_f′} en voor alle q_j ∈ Q′′ ∖ {q₀′} laat $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ waarbij R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Ga verder met stap 2.

Voorbeeld

Neem als invoer deze eindige automaat:

Eerst zetten we hem om in een GNFA (onnodige ∅-overgangen tekenen we niet):

Nu passen we het tweede deel van het algoritme toe en verwijderen we een knoop. We beginnen met knoop q₂. We verwijderen knoop q₂ en voegen een overgang toe van toestand q₁ naar toestand q_f. Deze overgang labelen we met b(a|b)^∗, want vanuit knoop q₁ komen we in toestand q₂ voor woorden van de vorm b, dan kunnen we rondlopen voor a|b, zo krijgen we (a|b)^∗ en tot slot gaan we met behulp van de epsilonregel naar q_f. Daarbij geldt b(a|b)^∗ϵ = b(a|b)^∗. We krijgen de automaat:

We hoeven alleen nog de laatste toestand, q₁, te verwijderen. We voegen een pijl toe van toestand q_s naar toestand q_f. Hoe labelen we die? Naar toestand q₁ komen we via de epsilonregel, die kunnen we meteen weglaten. Dan kunnen we rondlopen voor a, dus we krijgen de reguliere expressie a^∗. En tot slot komen we via de pijl in q_f, dus de expressie concateneren we nog met b(a|b)^∗. De pijl labelen we dus met de reguliere expressie a^∗ b(a|b)^∗.

De automaat heeft nog maar twee toestanden, dus het algoritme stopt. Op de pijl staat de resulterende reguliere expressie.

Bronnen

• Het voorbeeld en de beschrijving van het algoritme zijn afkomstig uit M. Sipser: Introduction to the Theory of Computation