Omvandling av NFA till DFA

Vi visar hur en icke-deterministisk automat kan omvandlas till en deterministisk automat. Därmed bevisar vi att icke-deterministiska och deterministiska automater har samma beräkningskraft.

Grundidén

Låt oss ta en icke-deterministisk automat ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ utan epsilonövergångar. Vi bygger en deterministisk automat ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ så att

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

Övergångsfunktionen δ_D definierar vi så här:

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

Vad betyder det? En icke-deterministisk automat kan befinna sig i flera tillstånd samtidigt, så vi kan till exempel hamna i en situation där vår icke-deterministiska automat är i tillstånden {q₀, q₁}. När vi läser nästa symbol, till exempel 1, kan vi komma till mängden av tillstånd {q₀, q₂, q₃}. I den deterministiska versionen av samma automat syns det genom att vi skapar två tillstånd, ger dem namnen {q₀, q₁} och {q₀, q₂, q₃} och inför en övergång mellan dem för symbolen 1. Formellt går vi från ett tillstånd till ett annat, men tack vare namngivningen vet vi att vi i den icke-deterministiska automaten skulle ha hamnat i två respektive tre tillstånd.

Exempel

Låt oss ta den här icke-deterministiska automaten:

För att konstruera den deterministiska automaten behöver vi framför allt bygga en ny övergångsfunktion. Till det använder vi en tabell där vi skriver in alla övergångar. I början ser tabellen ut så här:

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

I den vänstra kolumnen kommer vi i slutet av algoritmen att ha alla tillstånd i den deterministiska automaten. Den ifyllda tabellen bestämmer sedan övergångsfunktionen. Nu skriver vi in i tabellen vilka tillstånd vi kommer till om vi befinner oss i tillståndet {q₀} och indata är symbolerna 0 och 1.

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

Från q₀ går för symbolen 0 en övergång bara till q₁, medan den för symbolen 1 går till q₁ och q₂. Nu lägger vi till två nya tillstånd i tabellen: {q₁} och {q₁, q₂}. Varför? Så fort vi fyller i en mängd av tillstånd i tabellen som ännu inte finns i den vänstra kolumnen lägger vi till den mängden där.

$$\begin{array}{ccc}\text{tillstånd}/\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}$$

och fyller återigen i. För tillståndet {q₁, q₂} får vi inte glömma att kontrollera båda tillstånden, dvs. unionen av de tillstånd vi kommer till från q₁ och de tillstånd vi kommer till från q₂.

$$\begin{array}{ccc}\text{tillstånd}/\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 fick flera nya tillstånd som vi måste lägga till i tabellen:

$$\begin{array}{ccc}\text{tillstånd}/\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}$$

…och fyller återigen i övergångarna:

$$\begin{array}{ccc}\text{tillstånd}/\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}$$

Tillstånden {q₀, q₁, q₃}, {q₁} och {q₁,q₂} har vi redan, så vi lägger bara till tillståndet {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{tillstånd}/\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 lade inte till något nytt tillstånd, så tabellen är ifylld. Nu återstår bara att rita diagrammet. Den deterministiska automatens tillstånd står i den första kolumnen, och övergångarna för symbolerna 0 och 1 i de följande. Varje tillstånd som innehåller något sluttillstånd från den ursprungliga automaten blir också ett sluttillstånd i den här automaten. Det betyder att varje tillstånd som innehåller q₃ blir ett sluttillstånd. Automaten ser ut så här:

Vi kan visa att automaten verkligen fungerar som den ska. Vi försöker acceptera ordet 11001. I den deterministiska automaten går vi längs vägen

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

och automaten skulle acceptera ordet, eftersom det sista tillståndet {q₀, q₁, q₂, q₃} är ett sluttillstånd. I den icke-deterministiska automaten skulle vi under simuleringen hamna i samma tillstånd, dvs. vi skulle börja i q₀ och för symbolen 1 komma till tillstånden {q₁, q₂}. Nästa symbol 1 skulle ta oss till tillstånden {q₀,q₃} osv. för de följande tillstånden. Till slut skulle vi befinna oss i alla tillstånden {q₀, q₁, q₂, q₃} och automaten skulle acceptera ordet.

Källor

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