Omforming av NFA til DFA

Vi skal vise hvordan du omformer en ikke-deterministisk automat til en deterministisk automat, og dermed beviser vi at beregningskraften til ikke-deterministiske og deterministiske automater er ekvivalent.

Grunntanken

La oss ha en ikke-deterministisk automat ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ uten epsilonoverganger. Vi konstruerer en deterministisk automat ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ slik at

Q_D ⊆ 2^Q_N
Σ_D = Σ_N
p₀ = {q₀}
F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

Overgangsfunksjonen δ_D definerer vi som følger:

$\forall Q \in Q_{D}, a \in Σ_{D} : δ_{D} (Q, a) = ⋃_{q \in Q} δ_{N} (q, a)$

Hva betyr dette? En ikke-deterministisk automat kan være i flere tilstander samtidig, så vi kan for eksempel komme i en situasjon der den ikke-deterministiske automaten vår er i tilstandene {q₀, q₁}. Ved å lese neste symbol, for eksempel 1, kan vi komme til mengden av tilstander {q₀, q₂, q₃}. I den deterministiske versjonen av den samme automaten viser det seg ved at vi lager to tilstander, gir dem navnene {q₀, q₁} og {q₀, q₂, q₃} og innfører en overgang mellom dem for symbolet 1. Formelt kommer vi dermed fra én tilstand til en annen, men takket være navnene vet vi at vi i den ikke-deterministiske automaten ville havnet i henholdsvis to og tre tilstander.

Eksempel

La oss ha denne ikke-deterministiske automaten:

For å konstruere den deterministiske automaten må vi først og fremst konstruere en ny overgangsfunksjon. Til det har vi nytte av en tabell der vi skriver inn alle overgangene. I begynnelsen ser tabellen slik ut:

$\begin{array}{ccc} tilstand / symbol & 0 & 1 \\ {q_{0}} \end{array}$

I den venstre kolonnen vil vi på slutten av algoritmen ha alle tilstandene i den deterministiske automaten. Den utfylte tabellen bestemmer da overgangsfunksjonen. Nå skriver vi inn i tabellen hvilke tilstander vi kommer til hvis vi er i tilstanden {q₀} og symbolene 0 og 1 er input.

$\begin{array}{ccc} tilstand / symbol & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

Fra tilstanden q₀ går det for symbolet 0 en overgang bare til tilstanden q₁, mens det for symbolet 1 går overganger til tilstandene q₁ og q₂. Nå legger vi to nye tilstander til i tabellen: {q₁} og {q₁, q₂}. Hvorfor? Så snart vi fyller ut en mengde av tilstander som vi ennå ikke har i den venstre kolonnen, legger vi denne mengden av tilstander til der.

$\begin{array}{ccc} tilstand / symbol & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} \\ {q_{1}, q_{2}} \end{array}$

og vi fyller ut igjen. For tilstanden {q₁, q₂} må vi ikke glemme å sjekke begge tilstandene, altså hvor vi kommer fra tilstanden q₁, slått sammen med hvor vi kommer fra tilstanden q₂.

Vi fikk flere nye tilstander som vi må legge til i tabellen:

…og vi fyller ut overgangene igjen:

$\begin{array}{ccc} tilstand / symbol & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{3}} \\ {q_{1}, q_{2}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{3}} \\ {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{1}, q_{2}, q_{3}} \\ {q_{0}, q_{3}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

Tilstandene {q₀, q₁, q₃}, {q₁} og {q₁,q₂} har vi allerede der, så vi legger bare til tilstanden {q₀,q₁,q₂,q₃}.

Vi la ikke til noen ny tilstand denne gangen, så tabellen er ferdig utfylt. Nå gjenstår det bare å tegne diagrammet. Tilstandene i den deterministiske automaten står i den første kolonnen, og overgangene for symbolene 0 og 1 står i de neste. Hver tilstand som inneholder en sluttilstand fra den opprinnelige automaten, blir også en sluttilstand i denne automaten. Det betyr at hver tilstand som inneholder q₃, blir en sluttilstand. Automaten kommer til å se slik ut:

Vi kan vise at automaten virkelig fungerer riktig. Vi prøver å akseptere ordet 11001. I den deterministiske automaten går vi veien

$q_{0} \to^{1} q_{1}, q_{2} \to^{1} q_{0}, q_{3} \to^{0} q_{1} \to^{0} q_{0}, q_{1}, q_{3} \to^{1} q_{0}, q_{1}, q_{2}, q_{3}$

og automaten ville akseptert ordet, siden den siste tilstanden {q₀, q₁, q₂, q₃} er en sluttilstand. I den ikke-deterministiske automaten ville vi under simuleringen komme til de samme tilstandene, altså vi ville begynt i tilstanden q₀ og kommet til tilstandene {q₁, q₂} for symbolet 1. Det neste symbolet 1 ville tatt oss til tilstandene {q₀,q₃} osv. for de neste tilstandene. Til slutt ville vi havnet i alle tilstandene {q₀, q₁, q₂, q₃}, og automaten ville akseptert ordet.

Kilder

Kapitler: Endelig automat, Total automat, Ikke-deterministisk endelig automat, Simulering av ikke-deterministisk automat, Omforming av NFA til DFA

« Forrige: Simulering av ikke-deterministisk automat

Neste: Minimering av automater »