Zobecněný nedeterministický konečný automat - Generalized nondeterministic finite automaton

V teorii výpočtu je zobecněný nedeterministický konečný automat ( GNFA ), známý také jako výrazový automat nebo zobecněný nedeterministický konečný stavový stroj , variací nedeterministického konečného automatu (NFA), kde je každý přechod označen jakýmkoli regulárním výrazem . GNFA čte bloky symbolů ze vstupu, které tvoří řetězec definovaný regulárním výrazem na přechodu. Existuje několik rozdílů mezi standardním strojem s konečným stavem a zobecněným nedeterministickým strojem s konečným stavem. GNFA musí mít pouze jeden počáteční stav a jeden přijímací stav, a ty nemohou být stejný stát, zatímco NFA nebo DFA mohou mít několik přijímacích stavů a ​​počáteční stav může být stav přijetí. GNFA musí mít pouze jeden přechod mezi libovolnými dvěma státy, zatímco NFA nebo DFA oba umožňují četné přechody mezi státy. V GNFA má stát jediný přechod do každého stavu ve stroji, i když často se jedná o konvenci ignorování přechodů, které jsou označeny prázdnou sadou, když se kreslí generalizované nedeterministické stroje s konečným stavem.

Formální definice

GNFA mohou být definovány jako 5-n-tice , ( S , å, T , y , ), skládající se z

  • konečná množina stavů ( S );
  • konečná množina zvaná abeceda (Σ);
  • přechodová funkce ( T  : ( S ∖ { a }) × ( S ∖ { s }) → R );
  • počáteční stav ( s ∈ S );
  • stav přijetí ( a ∈ S );

kde R je sbírka všech regulárních výrazů nad abecedou Σ.

Funkce přechodu bere jako argument dvojici dvou stavů a ​​vydává regulární výraz (štítek přechodu). To se liší od ostatních strojů s konečným stavem, které berou jako vstup jeden stav a vstup z abecedy (nebo prázdný řetězec v případě nedeterministických strojů s konečným stavem) a výstupem dalšího stavu (nebo množiny možných stavů v případě nedeterministických konečných stavových strojů). DFA nebo NFA může být snadno přeměněna na GNFA a pak GNFA lze snadno převést na regulární výraz opakovaným padá částí to, aby jednotlivé hrany až do S = { s , několika }. Podobně lze GNFA snížit na NFA změnou operátorů regulárního výrazu na nové hrany, dokud nebude každá hrana označena regulárním výrazem odpovídajícím jedinému řetězci délky nejvýše 1. NFA lze zase redukovat na DFA pomocí konstrukce poweret . To ukazuje, že GNFA uznávají stejnou sadu formálních jazyků jako DFA a NFA.

Reference

externí odkazy

  • Grafický popis GNFA a procesu převodu NFA na regulární výraz pomocí GNFA najdete na [1]