Omzetting van NFA naar DFA

We laten zien hoe je een niet-deterministische automaat omzet naar een deterministische automaat. Daarmee bewijzen we dat niet-deterministische en deterministische automaten evenveel kunnen berekenen (dezelfde rekenkracht hebben).

Basisidee

Neem een niet-deterministische automaat ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ zonder epsilonovergangen. We bouwen een deterministische automaat ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ zo dat

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

De overgangsfunctie δ_D definiëren we als volgt:

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

Wat betekent dit? Een niet-deterministische automaat kan tegelijk in meerdere toestanden zijn, dus we kunnen bijvoorbeeld in de situatie komen dat onze niet-deterministische automaat in de toestanden {q₀, q₁} zit. Door het volgende symbool te lezen, bijvoorbeeld 1, kunnen we in de verzameling toestanden {q₀, q₂, q₃} komen. In de deterministische versie van dezelfde automaat komt dat tot uiting doordat we twee toestanden maken, ze {q₀, q₁} en {q₀, q₂, q₃} noemen en daartussen een overgang voor het symbool 1 invoeren. Formeel gaan we zo van de ene toestand naar de andere, maar dankzij de naamgeving weten we dat we in de niet-deterministische automaat in twee, respectievelijk drie toestanden zouden zitten.

Voorbeeld

Neem deze niet-deterministische automaat:

Om de deterministische automaat te construeren, moeten we vooral een nieuwe overgangsfunctie opstellen. Daarbij helpt een tabel waarin we alle overgangen noteren. Aan het begin ziet de tabel er zo uit:

$\begin{array}{ccc} toestand / symbool & 0 & 1 \\ {q_{0}} \end{array}$

In de linkerkolom staan aan het einde van het algoritme alle toestanden van de deterministische automaat. De ingevulde tabel bepaalt dan de overgangsfunctie. Nu noteren we in de tabel in welke toestanden we komen als we in de toestanden {q₀} zitten en de invoer de symbolen 0 en 1 is.

$\begin{array}{ccc} toestand / symbool & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

Vanuit toestand q₀ loopt voor het symbool 0 alleen een overgang naar toestand q₁, terwijl er voor het symbool 1 overgangen lopen naar de toestanden q₁ en q₂. Nu voegen we twee nieuwe toestanden aan de tabel toe: {q₁} en {q₁, q₂}. Waarom? Zodra we in de tabel een verzameling toestanden invullen die nog niet in de linkerkolom staat, voegen we die verzameling toestanden daar toe.

$\begin{array}{ccc} toestand / symbool & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} \\ {q_{1}, q_{2}} \end{array}$

en we vullen weer in. Bij de toestand {q₁, q₂} mogen we niet vergeten beide toestanden te controleren, dus waar we vanuit toestand q₁ komen, verenigd met waar we vanuit toestand q₂ komen.

We hebben een aantal nieuwe toestanden gekregen, die we aan de tabel moeten toevoegen:

…en we vullen de overgangen weer in:

$\begin{array}{ccc} toestand / symbool & 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}$

De toestanden {q₀, q₁, q₃}, {q₁} en {q₁,q₂} hebben we al, dus we voegen alleen de toestand {q₀,q₁,q₂,q₃} toe.

We hebben geen nieuwe toestand meer toegevoegd, dus de tabel is ingevuld. Nu hoeven we alleen nog het diagram te tekenen. De toestanden van de deterministische automaat staan in de eerste kolom, de overgangen voor de symbolen 0 en 1 in de volgende. Elke toestand die een eindtoestand van de oorspronkelijke automaat bevat, is ook in deze automaat een eindtoestand. Dat wil zeggen dat elke toestand die q₃ bevat een eindtoestand wordt. De automaat ziet er zo uit:

We kunnen laten zien dat de automaat echt goed werkt. We proberen het woord 11001 te accepteren. In de deterministische automaat volgen we het pad

$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}$

en de automaat zou het woord accepteren, omdat de laatste toestand {q₀, q₁, q₂, q₃} een eindtoestand is. In de niet-deterministische automaat zouden we tijdens de simulatie in dezelfde toestanden komen: we zouden beginnen in toestand q₀ en voor het symbool 1 in de toestanden {q₁, q₂} komen. Het volgende symbool 1 zou ons in de toestanden {q₀,q₃} brengen enzovoort voor de volgende toestanden. Uiteindelijk zouden we in alle toestanden {q₀, q₁, q₂, q₃} belanden en de automaat zou het woord accepteren.

Bronnen

Hoofdstukken: Eindige automaat, Totale automaat, Niet-deterministische eindige automaat, Simulatie van een niet-deterministische automaat, Omzetting van NFA naar DFA

« Vorige: Simulatie van een niet-deterministische automaat

Volgende: Minimalisatie van automaten »