I dette afsnit vil vi diskutere metoden til at konvertere NFA til dets tilsvarende DFA. I NFA, når der gives et specifikt input til den aktuelle tilstand, går maskinen til flere tilstande. Det kan have nul, et eller mere end et træk på et givet inputsymbol. På den anden side, i DFA, når der gives et specifikt input til den aktuelle tilstand, går maskinen kun til én tilstand. DFA har kun ét træk på et givet inputsymbol.

download youtube video med vlc

Lad, M = (Q, ∑, δ, q0, F) er en NFA, som accepterer sproget L(M). Der bør være ækvivalent DFA angivet med M' = (Q', ∑', q0', δ', F'), således at L(M) = L(M').

Trin til konvertering af NFA til DFA:

Trin 1: Indledningsvis Q' = ϕ

Trin 2: Tilføj q0 af NFA til Q'. Find derefter overgangene fra denne starttilstand.

Trin 3: I Q', find det mulige sæt af tilstande for hvert inputsymbol. Hvis dette sæt af tilstande ikke er i Q', skal du tilføje det til Q'.

Trin 4: I DFA vil den endelige tilstand være alle de stater, der indeholder F (sluttilstande af NFA)

Eksempel 1:

Konverter den givne NFA til DFA.

Løsning: For det givne overgangsdiagram vil vi først konstruere overgangstabellen.

Nu får vi δ'-overgang for tilstand q0.

 δ'([q0], 0) = [q0] δ'([q0], 1) = [q1] 

δ'-overgangen for tilstand q1 opnås som:

boble sortering i algoritme

 δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1] 

δ'-overgangen for tilstand q2 opnås som:

 δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2] 

Nu får vi δ'-overgang på [q1, q2].

 δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0) = {q1, q2} ∪ {q2} = [q1, q2] δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1} ∪ {q1, q2} = {q1, q2} = [q1, q2] 

Tilstanden [q1, q2] er også den endelige tilstand, fordi den indeholder en sluttilstand q2. Overgangstabellen for den konstruerede DFA vil være:

Overgangsdiagrammet vil være:

Tilstanden q2 kan elimineres, fordi q2 er en tilstand, der ikke kan nås.

Eksempel 2:

Konverter den givne NFA til DFA.

Løsning: For det givne overgangsdiagram vil vi først konstruere overgangstabellen.

java hvordan man konverterer streng til int

Nu får vi δ'-overgang for tilstand q0.

 δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] 

δ'-overgangen for tilstand q1 opnås som:

 δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1] 

Nu vil vi opnå δ'-overgang på [q0, q1].

 δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] 

Tilsvarende

 δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] 

Som i den givne NFA er q1 en endelig tilstand, så i DFA hvor som helst, hvor q1 eksisterer, bliver denne tilstand en endelig tilstand. Derfor er sluttilstande i DFA [q1] og [q0, q1]. Derfor sæt af sluttilstande F = {[q1], [q0, q1]}.

10 af 50

Overgangstabellen for den konstruerede DFA vil være:

Overgangsdiagrammet vil være:

Selv vi kan ændre navnet på staterne i DFA.

Formode

 A = [q0] B = [q1] C = [q0, q1] 

Med disse nye navne bliver DFA som følger: