Zobecněný nedeterministický konečný automat

Zobecněný nedeterministický konečný automat, zkráceně ZNKA, je nedeteministický automat, který v přechodech nemusí mít pouze symboly z jazyka, ale může tam mít regulární výraz.

Definice

ZNKA budeme potřebovat během algoritmu pro převod konečného automatu na regulární výraz. ZNKA je tak NKA, který má přechody definované regulárními výrazy. Příklad takového ZNKA:

Vidíme, že např. ze stavu q₂ vede přechod do stavu q₃ a je označený regulárním výrazem $a^\ast b$. Další požadavky na ZNKA:

• Počáteční stav q₀ musí mít přechod do všech ostatní stavů. Na obrázku vidíme, že ze stavu q₀ vedou přechody do všech ostatních stavů.
• V ZNKA existuje pouze jeden koncový stav a všechny ostatní stavy mají do tohoto stavu přechod. Jak je vidět na obrázku, všechny stavy mají šipku směřující do q_f.
• Počáteční stav nesmí být shodný s koncovým stavem. ZNKA tak může mít nejméně dva stavy.
• Všechny ostatní stavy, kromě počátečního a koncového, musí mít přechody do všech ostatních stavů, kromě počátečního a koncového. Včetně smyček (přechod ze stavu q_i do stavu q_i).

Převod běžného NKA na ZNKA

Pokud máme nějaký NKA, je převod na ZNKA jednoduchý.

1. Vytvoříme nový počáteční stav q_s a vytvoříme epsilon přechod do původního počátečního stavu.
2. Vytvoříme nový koncový stav q_f a ze všech původních koncových stavů povedeme epsilon přechody do stavu q_f. Z původních koncových stavů uděláme normální stavy.
3. Pokud někde existuje vícenásobný přechod (tj. pokud se ze stavu q₁ dostaneme do stavu q₂ přes symbol 0 i přes symbol 1), tak tato pravidla sloučíme do jednoho regulárního výrazu a všechny původní symboly spojíme operátorem sjednocení (tj. označíme šipku regulárním výrazem 0|1).
4. Pokud v automatu chybí nějaký přechod, který by tam dle definice mít, vytvoříme ho a označíme ho regulárním výrazem ∅. Tím nezměníme jazyk, který automat přijímá, protože takový přechod se nikdy neprovede.

Tento automat můžeme použít pro převod automatu na regulární výraz.