I det här avsnittet kommer vi att diskutera metoden för att konvertera NFA till motsvarande DFA. I NFA, när en specifik ingång ges till det aktuella tillståndet, går maskinen till flera tillstånd. Den kan ha noll, ett eller flera drag på en given ingångssymbol. Å andra sidan, i DFA, när en specifik ingång ges till det aktuella tillståndet, går maskinen till endast ett tillstånd. DFA har bara ett drag på en given ingångssymbol.
Låt, M = (Q, ∑, δ, q0, F) är en NFA som accepterar språket L(M). Det bör finnas ekvivalent DFA betecknad med M' = (Q', ∑', q0', δ', F') så att L(M) = L(M').
Steg för att konvertera NFA till DFA:
Steg 1: Initialt Q' = ϕ
Steg 2: Lägg till q0 av NFA till Q'. Hitta sedan övergångarna från detta startläge.
hur man visar en applikation på Android
Steg 3: I Q', hitta den möjliga uppsättningen av tillstånd för varje ingångssymbol. Om denna uppsättning tillstånd inte är i Q', lägg till den i Q'.
Steg 4: I DFA kommer det slutliga tillståndet att vara alla tillstånd som innehåller F (sluttillstånd för NFA)
Exempel 1:
Konvertera den givna NFA till DFA.
Lösning: För det givna övergångsdiagrammet kommer vi först att konstruera övergångstabellen.
| stat | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Nu kommer vi att få δ'-övergång för tillstånd q0.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
δ'-övergången för tillstånd q1 erhålls som:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
δ'-övergången för tillstånd q2 erhålls som:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Nu kommer vi att få δ'-övergång 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] Tillståndet [q1, q2] är också sluttillståndet eftersom det innehåller ett sluttillstånd q2. Övergångstabellen för den konstruerade DFA kommer att vara:
| stat | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Övergångsdiagrammet kommer att vara:
Tillståndet q2 kan elimineras eftersom q2 är ett oåtkomligt tillstånd.
Exempel 2:
Konvertera den givna NFA till DFA.
all caps genväg excel
Lösning: För det givna övergångsdiagrammet kommer vi först att konstruera övergångstabellen.
| stat | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Nu kommer vi att få δ'-övergång för tillstånd q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] δ'-övergången för tillstånd q1 erhålls som:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Nu kommer vi att få δ'-övergång på [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Liknande,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Som i den givna NFA är q1 ett sluttillstånd, sedan i DFA, varhelst q1 existerar, blir det tillståndet ett sluttillstånd. Därför är sluttillstånden i DFA [q1] och [q0, q1]. Därför uppsättning sluttillstånd F = {[q1], [q0, q1]}.
Övergångstabellen för den konstruerade DFA kommer att vara:
t ff
| stat | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Övergångsdiagrammet kommer att vara:
Även vi kan ändra namnet på delstaterna i DFA.
Anta
A = [q0] B = [q1] C = [q0, q1]
Med dessa nya namn blir DFA följande:
