PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Zobecněný nedeterministický konečný automat

Zobrazit kapitoly článku
  1. Regulární výrazy
  2. Převod reguláru na automat
  3. Zobecněný NKA
  4. Převod automat na regulár

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 q2 vede přechod do stavu q3 a je označený regulárním výrazem \(a^\ast b\). Další požadavky na ZNKA:

  • Počáteční stav q0 musí mít přechod do všech ostatní stavů. Na obrázku vidíme, že ze stavu q0 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 qf.
  • 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 qi do stavu qi).

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 qs a vytvoříme epsilon přechod do původního počátečního stavu.
  2. Vytvoříme nový koncový stav qf a ze všech původních koncových stavů povedeme epsilon přechody do stavu qf. 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 q1 dostaneme do stavu q2 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 \(\emptyset\). 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.

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace