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ść.
| Państwo | 0 | 1 |
|---|---|---|
| →q0 | q0 | pytanie 1 |
| pytanie 1 | {q1, q2} | pytanie 1 |
| *q2 | q2 | {q1, q2} |
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:
| Państwo | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
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ść.
| Państwo | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
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:
| Państwo | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
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:
