Omdannelse af NFA til DFA

Vi viser, hvordan man omdanner en ikke-deterministisk automat til en deterministisk automat, hvormed vi beviser, at beregningskraften hos ikke-deterministiske og deterministiske automater er ækvivalent.

Grundidé

Vi har en ikke-deterministisk automat ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ uden epsilon-overgange. Vi konstruerer en deterministisk automat ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ således, at

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

Overgangsfunktionen δ_D definerer vi på følgende måde:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

Hvad betyder det? En ikke-deterministisk automat kan være i flere tilstande på samme tid, så vi kan for eksempel komme i en situation, hvor vores ikke-deterministiske automat er i tilstandene {q₀, q₁}. Ved at læse det næste symbol, for eksempel 1, kan vi komme til mængden af tilstande {q₀, q₂, q₃}. I den deterministiske version af den samme automat viser det sig ved, at vi laver to tilstande, navngiver dem {q₀, q₁} og {q₀, q₂, q₃} og indfører en overgang mellem dem for symbolet 1. Formelt kommer vi fra den ene tilstand til den anden, men takket være navngivningen ved vi, at vi i den ikke-deterministiske automat ville være havnet i to, henholdsvis tre tilstande.

Eksempel

Vi ser på denne ikke-deterministiske automat:

For at konstruere den deterministiske automat skal vi først og fremmest konstruere en ny overgangsfunktion. Til det bruger vi en tabel, som vi skriver alle overgange ind i. I begyndelsen ser tabellen sådan ud:

$$\begin{array}{ccc}\text{tilstand}/\text{symbol}& 0& 1\\ \left\{q_0\right\}\end{array}$$

I den venstre søjle vil vi til sidst i algoritmen have alle tilstande i den deterministiske automat. Den udfyldte tabel vil så bestemme overgangsfunktionen. Nu skriver vi i tabellen, hvilke tilstande vi kommer til, hvis vi er i tilstandene {q₀} og inputsymbolerne er 0 og 1.

$$\begin{array}{ccc}\text{tilstand}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Fra tilstanden q₀ går der for symbolet 0 kun en overgang til tilstanden q₁, mens der for symbolet 1 går overgange til tilstandene q₁ og q₂. Nu tilføjer vi to nye tilstande til tabellen: {q₁} og {q₁, q₂}. Hvorfor? I det øjeblik, vi i tabellen udfylder en mængde af tilstande, som vi ikke endnu har i den venstre søjle, tilføjer vi denne mængde af tilstande dertil.

$$\begin{array}{ccc}\text{tilstand}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

og vi udfylder igen. Ved tilstanden {q₁, q₂} må vi ikke glemme at kontrollere begge tilstande, dvs. hvor vi kommer hen fra tilstanden q₁ forenet med, hvor vi kommer hen fra tilstanden q₂.

$$\begin{array}{ccc}\text{tilstand}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Vi fik nogle nye tilstande, som vi skal tilføje til tabellen:

$$\begin{array}{ccc}\text{tilstand}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{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_3\}\end{array}$$

…og vi udfylder igen overgangene:

$$\begin{array}{ccc}\text{tilstand}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{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\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Tilstandene {q₀, q₁, q₃}, {q₁} og {q₁,q₂} har vi allerede der, så vi tilføjer bare tilstanden {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{tilstand}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{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\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Vi tilføjede ikke flere nye tilstande, så tabellen er udfyldt. Nu mangler vi bare at tegne diagrammet. Tilstandene i den deterministiske automat står i den første søjle, overgangene for symbolerne 0 og 1 i de næste. Hver tilstand, der indeholder en accepttilstand fra den oprindelige automat, bliver også en accepttilstand i denne automat. Dvs. at hver tilstand, der indeholder q₃, bliver en accepttilstand. Automaten kommer til at se sådan ud:

Vi kan vise, at automaten virker helt korrekt. Vi prøver at acceptere ordet 11001. I den deterministiske automat går vi ad vejen

$$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 acceptere ordet, fordi den sidste tilstand {q₀, q₁, q₂, q₃} er accepterende. I den ikke-deterministiske automat ville vi under simuleringen komme til de samme tilstande, dvs. vi ville begynde i tilstanden q₀, og for symbolet 1 ville vi komme til tilstandene {q₁, q₂}. Det næste symbol 1 ville føre os til tilstandene {q₀,q₃} osv. for de følgende tilstande. Til sidst ville vi ende i alle tilstandene {q₀, q₁, q₂, q₃}, og automaten ville acceptere ordet.

Kilder

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools