V této části probereme metodu převodu NFA na ekvivalentní DFA. V NFA, když je dán konkrétní vstup aktuálnímu stavu, stroj přejde do více stavů. Může mít nula, jeden nebo více než jeden pohyb na daném vstupním symbolu. Na druhou stranu v DFA, když je dán konkrétní vstup aktuálnímu stavu, stroj přejde pouze do jednoho stavu. DFA má pouze jeden pohyb na daném vstupním symbolu.
Nechť, M = (Q, ∑, δ, q0, F) je NFA, která přijímá jazyk L(M). Měl by existovat ekvivalentní DFA označený M' = (Q', ∑', q0', 5', F') tak, že L(M) = L(M').
Kroky pro převod NFA na DFA:
Krok 1: Zpočátku Q' = ϕ
Krok 2: Přidejte q0 NFA do Q'. Poté najděte přechody z tohoto počátečního stavu.
srovnání java
Krok 3: V Q' najděte možnou sadu stavů pro každý vstupní symbol. Pokud tato sada stavů není v Q', přidejte ji do Q'.
Krok 4: V DFA budou konečným stavem všechny státy, které obsahují F (finální stavy NFA)
Příklad 1:
Převeďte daný NFA na DFA.
Řešení: Pro daný přechodový diagram nejprve zkonstruujeme přechodovou tabulku.
| Stát | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Nyní získáme přechod δ' pro stav q0.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
Přechod δ' pro stav q1 se získá takto:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
Přechod δ' pro stav q2 se získá takto:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Nyní získáme přechod δ' 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] Stav [q1, q2] je také konečný, protože obsahuje konečný stav q2. Přechodová tabulka pro vytvořenou DFA bude:
| Stát | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Diagram přechodu bude:
Stav q2 lze odstranit, protože q2 je nedosažitelný stav.
Příklad 2:
Převeďte daný NFA na DFA.
kontrola java je nulová
Řešení: Pro daný přechodový diagram nejprve zkonstruujeme přechodovou tabulku.
| Stát | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Nyní získáme přechod δ' pro stav q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] Přechod δ' pro stav q1 se získá takto:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Nyní získáme přechod δ' na [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Podobně,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Stejně jako v daném NFA je q1 konečný stav, pak v DFA, kdekoli existuje q1, se tento stav stává konečným stavem. V DFA jsou tedy konečné stavy [q1] a [q0, q1]. Tedy množina konečných stavů F = {[q1], [q0, q1]}.
Přechodová tabulka pro vytvořenou DFA bude:
nový řádek python
| Stát | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Diagram přechodu bude:
I my můžeme změnit názvy států DFA.
Předpokládat
A = [q0] B = [q1] C = [q0, q1]
S těmito novými názvy bude DFA vypadat následovně:
