NFA může mít nula, jeden nebo více než jeden pohyb z daného stavu na daném vstupním symbolu. NFA může mít také pohyby NULL (pohyby bez vstupního symbolu). Na druhou stranu DFA má jeden a pouze jeden pohyb z daného stavu na daném vstupním symbolu.

Kroky pro převod NFA na DFA:

Krok 1: Převeďte daný NFA na jeho ekvivalentní tabulku přechodů
Abychom převedli NFA na ekvivalentní tabulku přechodu, musíme vypsat všechny stavy, vstupní symboly a pravidla přechodu. Pravidla přechodu jsou znázorněna ve formě matice, kde řádky představují aktuální stav, sloupce představují vstupní symbol a buňky představují další stav.

Krok 2: Vytvořte počáteční stav DFA
Počáteční stav DFA je sada všech možných počátečních stavů v NFA. Tato sada se nazývá epsilon uzavření počátečního stavu NFA. Uzávěr epsilon je množina všech stavů, kterých lze dosáhnout z počátečního stavu následujícími přechody epsilon (?).

srovnání java

Krok 3: Vytvořte tabulku přechodu DFA
Přechodová tabulka DFA je podobná přechodové tabulce NFA, ale místo jednotlivých stavů představují řádky a sloupce sady stavů. Pro každý vstupní symbol obsahuje odpovídající buňka v přechodové tabulce epsilonový uzávěr množiny stavů získaných dodržením přechodových pravidel v přechodové tabulce NFA.

Krok 4: Vytvořte konečné stavy DFA
Konečné stavy DFA jsou sady stavů, které obsahují alespoň jeden konečný stav z NFA.

Krok 5: Zjednodušte DFA
DFA získaná v předchozích krocích může obsahovat zbytečné stavy a přechody. Pro zjednodušení DFA můžeme použít následující techniky:

kontrola java je nulová

• Odebrat nedosažitelné stavy: Stavy, které nelze dosáhnout z počátečního stavu, lze ze služby DFA odstranit.
• Odstranit mrtvé stavy: Stavy, které nemohou vést ke konečnému stavu, lze ze služby DFA odstranit.
• Sloučit ekvivalentní stavy: Stavy, které mají stejná pravidla přechodu pro všechny vstupní symboly, lze sloučit do jednoho stavu.

Krok 6: Opakujte kroky 3-5, dokud nebude možné další zjednodušení
Po zjednodušení DFA opakujeme kroky 3–5, dokud nebude možné další zjednodušení. Výsledná získaná DFA je minimalizovaný ekvivalent DFA k danému NFA.

Příklad: Zvažte následující NFA znázorněné na obrázku 1.

Následují různé parametry pro NFA. Q = { q0, q1, q2}? = (a, b) F = { q2}? (Přechodová funkce NFA)

Krok 1: Q' = ? Krok 2: Q’ = {q0} Krok 3: Pro každý stav v Q’ najděte stavy pro každý vstupní symbol. Aktuálně je stav v Q' q0, najděte pohyby z q0 na vstupním symbolu aab pomocí přechodové funkce NFA a aktualizujte tabulku přechodů DFA. ?‘ (Přechodová funkce DFA)

Nyní { q0, q1 } bude považováno za jeden stav. Protože jeho záznam není v Q', přidejte ho do Q'. Takže Q' = { q0, { q0, q1 } } Nyní, pohyby ze stavu { q0, q1 } na různých vstupních symbolech nejsou přítomny v tabulce přechodů DFA, vypočítáme to jako: ?' ( { q0, q1 } , a) = ? (q0, a)? ? ( q1, a ) = { q0, q1 } ?‘ ( { q0, q1 }, b ) = ? (q0, b)? ? ( q1, b ) = { q0, q2 } Nyní aktualizujeme tabulku přechodů DFA. ?‘ (Přechodová funkce DFA)

nový řádek python

Nyní { q0, q2 } bude považováno za jeden stav. Protože jeho záznam není v Q', přidejte ho do Q'. Takže Q' = { q0, { q0, q1 }, { q0, q2 } } Nyní, pohyby ze stavu {q0, q2} na různých vstupních symbolech nejsou v tabulce přechodů DFA přítomny, vypočítáme to jako: ?' ( { q0, q2 }, a ) = ? (q0, a)? ? ( q2, a ) = { q0, q1 } ?‘ ( { q0, q2 }, b ) = ? (q0, b)? ? ( q2, b ) = { q0 } Nyní aktualizujeme tabulku přechodů DFA. ?‘ (Přechodová funkce DFA)

Protože není vygenerován žádný nový stav, je převod hotový. Konečným stavem DFA bude stav, jehož součástí je q2, tj. { q0, q2 } Dále jsou uvedeny různé parametry pro DFA. Q’ = { q0, { q0, q1 }, { q0, q2 } } ? = (a, b) F = { { q0, q2 } } a přechodová funkce ?‘, jak je uvedeno výše. Konečná DFA pro výše uvedený NFA je znázorněna na obrázku 2.

Poznámka : Někdy není snadné převést regulární výraz do DFA. Nejprve můžete převést regulární výraz na NFA a poté NFA na DFA.

otázka: Počet stavů v minimálním deterministickém konečném automatu odpovídajících regulárnímu výrazu (0 + 1)* (10) je ____________.

Řešení : Nejprve vytvoříme NFA pro výše uvedený výraz. Pro vytvoření NFA pro (0 + 1)* bude NFA ve stejném stavu q0 na vstupním symbolu 0 nebo 1. Poté pro zřetězení přidáme dva tahy (q0 až q1 pro 1 a q1 až q2 pro 0), jak je znázorněno na obrázku 3.

K tomuto článku přispěl Sonal Tuteja.