W tej sekcji omówimy metodę konwersji NFA na jego odpowiednik DFA. W NFA, gdy do bieżącego stanu zostanie podany określony sygnał wejściowy, maszyna przechodzi do wielu stanów. Może mieć zero, jeden lub więcej niż jeden ruch na danym symbolu wejściowym. Z drugiej strony w DFA, gdy określone dane wejściowe zostaną podane do bieżącego stanu, maszyna przechodzi tylko do jednego stanu. DFA ma tylko jeden ruch na danym symbolu wejściowym.

Niech, M = (Q, ∑, δ, q0, F) jest NFA, które akceptuje język L(M). Powinien istnieć równoważny DFA oznaczony przez M' = (Q', ∑', q0', δ', F') taki, że L(M) = L(M').

Kroki konwersji NFA na DFA:

Krok 1: Początkowo Q' = ϕ

Krok 2: Dodaj q0 NFA do Q'. Następnie znajdź przejścia z tego stanu początkowego.

Krok 3: W Q' znajdź możliwy zbiór stanów dla każdego symbolu wejściowego. Jeżeli tego zbioru stanów nie ma w Q', to dodaj go do Q'.

Krok 4: W DFA stanem końcowym będą wszystkie stany zawierające F (stany końcowe NFA)

Przykład 1:

Konwertuj podany NFA na DFA.

Rozwiązanie: Dla danego diagramu przejść najpierw skonstruujemy tabelę przejść.

Otrzymamy teraz przejście δ' dla stanu q0.

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

Przejście δ' dla stanu q1 uzyskuje się jako:

Numer 1 milion

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

Przejście δ' dla stanu q2 uzyskuje się jako:

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

Otrzymamy teraz przejście δ' na [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] 

Stan [q1, q2] jest także stanem końcowym, ponieważ zawiera stan końcowy q2. Tabela przejściowa dla skonstruowanego DFA będzie wyglądać następująco:

Schemat przejścia będzie wyglądał następująco:

Stan q2 można wyeliminować, ponieważ q2 jest stanem nieosiągalnym.

Przykład 2:

Konwertuj podany NFA na DFA.

Rozwiązanie: Dla danego diagramu przejść najpierw skonstruujemy tabelę przejść.

Otrzymamy teraz przejście δ' dla stanu q0.

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

Przejście δ' dla stanu q1 uzyskuje się jako:

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

Otrzymamy teraz przejście δ' na [q0, q1].

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

Podobnie,

przykładowy JavaScript

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

Tak jak w danym NFA, q1 jest stanem końcowym, to w DFA gdziekolwiek istnieje q1, stan ten staje się stanem końcowym. Stąd w DFA stanami końcowymi są [q1] i [q0, q1]. Zatem zbiór stanów końcowych F = {[q1], [q0, q1]}.

Tabela przejściowa dla skonstruowanego DFA będzie wyglądać następująco:

Schemat przejścia będzie wyglądał następująco:

Nawet my możemy zmienić nazwę stanów DFA.

Przypuszczać

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

Dzięki tym nowym nazwom DFA będzie wyglądać następująco: