Nedeterministický stavový automat

Nedeterministický konečný automat (NFA, angl. nedeterministický konečný automat , NFA) je deterministický konečný automat (DFA, angl. deterministický konečný automat , DFA), který nesplňuje následující podmínky:

kterýkoli z jeho přechodů je jednoznačně určen aktuálním stavem a vstupním symbolem
pro každou změnu stavu je vyžadováno čtení vstupního znaku.

Konkrétně každá DFA je také NFA.

Pomocí algoritmu konstrukce podmnožiny lze libovolnou NFA převést na ekvivalentní DFA, tedy DFA, která rozpoznává stejný formální jazyk [1] . Stejně jako DFA rozpoznává NFA pouze běžné jazyky .

NFA byl navržen v roce 1959 Michaelem O. Rabinem a Danou Scott [2] , kteří ukázali, že je ekvivalentní k DFA. NFA se používá při implementaci regulárních výrazů - Thompsonova konstrukce je algoritmus pro převod regulárního výrazu na NFA, který dokáže efektivně rozpoznat vzor řetězců. Naopak, Kleeneův algoritmus lze použít k transformaci NFA na regulární výraz , jehož velikost obecně závisí exponenciálně na velikosti automatu.

NFA je zobecněna mnoha způsoby, například: nedeterministické konečné automaty s ε-přechody , konečné převodníky, zásobníkové automaty , střídavé automaty, ω-automaty a pravděpodobnostní automaty . Kromě DFA jsou známy další speciální případy NFA - jednoznačné konečné automaty ( angl. jednoznačné konečné automaty , UFA) a samoověřovací konečné automaty ( angl. self -verifying finite automata , SVFA).

Neformální úvod

Existuje několik neformálních ekvivalentních popisů:

NFA, stejně jako DFA , přebírá řetězec vstupních znaků. Pro každý vstupní symbol přechází do nového stavu, dokud nezpracuje všechny vstupní symboly. V každém kroku si automat náhodně vybere jeden z možných přechodů. Pokud dojde k "nadějnému průchodu", to je nějaká sekvence voleb vedoucí ke konečnému stavu poté, co byl vstupní řetězec plně načten, pak je řetězec přijat. Pokud neexistuje sekvence, která by po zpracování celého vstupního řetězce [3] přivedla automat do konečného stavu, pak je vstupní řetězec odmítnut [4] [5] .
Nechte NFA znovu vzít řetězec vstupních znaků, jeden znak za druhým. V každém kroku, kdy se dva nebo více přechodů ukáží jako platné, se automat „naklonuje“ do požadovaného počtu kopií, z nichž každá provádí jiné přechody. Pokud nelze provést žádný přechod, aktuální kopie je ve slepé uličce a zaniká. Pokud po načtení všech znaků ze vstupního řetězce přejde některá z kopií do finálního stavu, je vstupní řetězec akceptován, v opačném případě je zamítnut [6] [7] [8] .

Formální definice

Pro elementárnější úvod do formální definice viz článek " Teorie automatů ".

Automaty

NFA je formálně reprezentován jako 5-ti skládající se z: $(Q,\Sigma ,\Delta ,q_{0},F)$

konečná množina stavů . $Q$
konečná množina vstupních symbolů . $\Sigma$
přechodové funkce : . $\Delta$ $Q\times \Sigma \rightarrow P(Q)$
výchozí stav . $q_{0}\in Q$
soubory stavů rozpoznatelných jako konečné stavy . $F$ $F\subseteq Q$

Zde znamená stupeň sady . $P(Q)$ $Q$

Rozpoznaný jazyk

Daný NFA rozpozná jazyk, který je označen jako a definovaný jako množina všech řetězců v abecedě akceptovaných automatem . $M=(Q,\Sigma ,\Delta ,q_{0},F)$ $L(M)$ $\Sigma$ $M$

Obecně řečeno, podle výše uvedených neformálních vysvětlení existuje několik ekvivalentních formálních definic řetězců akceptovaných automatem : ${\displaystyle w=a_{1}a_{2}...a_{n))$ $M$

$w$ je přijat, pokud existuje posloupnost stavů v takovém, že ${\displaystyle r_{0},r_{1},...,r_{n))$ $Q$
1. $r_{0}=q_{0}$
2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$ , pro $i=0,\ldots ,n-1$
3. $r_{n}\in F$ .

Slova. První podmínka říká, že stroj startuje ze stavu . Druhá podmínka říká, že pro každý znak v řetězci stroj přechází ze stavu do stavu podle přechodové funkce . Poslední podmínka říká, že stroj přijme řetězec , pokud vstupní řetězec způsobí ukončení stroje v jeho konečném stavu. Aby byl řetězec akceptován automatem , není vyžadováno, aby jakákoli sekvence stavů končila v konečném stavu, stačí, aby jedna sekvence k takovému stavu vedla. V opačném případě, tj . pokud není možné přejít z do stavu z , po , automat říká, že odmítne řetězec. Množina řetězců, kterou automat akceptuje , je jazyk rozpoznávaný automatem a tento jazyk je označen jako [9] [10] .

q_{0}

w

\Delta

w

w

w

M

q_{0}

F

w

M

M

L(M)

Alternativně je akceptováno, pokud , kde je definováno rekurzivně : $w$ $\Delta ^{*}(q_{0},w)\cap F\not =\emptyset$ $\Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)$
1. ${\displaystyle \Delta ^{*}(r,\epsilon )=\{r\))$ , kde je prázdný řetězec $\epsilon$
2. $\Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)$ pro jakýkoli . $x\in \Sigma ^{*},a\in \Sigma$

Jinými slovy, je množina všech stavů dosažitelná ze stavu při získávání řetězce . Řetězec je akceptován, pokud lze dosáhnout nějakého koncového stavu z počátečního stavu pro vstupní řetězec [11] [12] .

\Delta ^{*}(r,x)

r

X

w

F

q_{0}

w

Počáteční stav

Výše uvedená definice automatu používá jeden počáteční stav , který není podmínkou. Někdy je NFA definována sadou počátečních stavů. Existuje jednoduchá konstrukce , která převádí NFA s více počátečními stavy na NFA s jediným počátečním stavem.

Příklad

Následující automat binární abecedy určuje, zda vstupní řetězec končí jedničkou. Nechť , kde přechodovou funkci lze definovat pomocí následující tabulky přechodů stavů (srovnej s horním obrázkem vlevo): $M$ $M=(\{p,q\},\{0,1\},\Delta ,p,\{q\})$ $\Delta$

VchodStát	0	jeden
$p$	${\displaystyle \{p\))$	${\displaystyle \{p,q\))$
$q$	$\emptyset$	$\emptyset$

Protože množina obsahuje více než jeden stav, je automat nedeterministický. Jazyk automatu lze popsat jako regulární jazyk daný regulárním výrazem . $\Delta(p,1)$ $M$ $M$ (0|1)*1

Všechny možné stavové sekvence pro vstupní řetězec "1011" jsou znázorněny na obrázku níže. Řetězec je akceptován automatem, protože jedna ze stavových sekvencí splňuje výše uvedenou definici. Nevadí, že ostatní sekvence neuspějí. Výkres lze interpretovat dvěma způsoby: $M$

Pokud jde o výše uvedené vysvětlení „šťastného běhu“ , každá cesta na obrázku představuje posloupnost voleb . $M$
Pro vysvětlení z hlediska "klonování", každý svislý sloupec ukazuje všechny klony automatu v daném čase, několik šipek vycházejících z uzlu znamená klonování, uzel bez odchozích šipek znamená "smrt" klonu. $M$

Schopnost číst stejný obrázek dvěma způsoby také ukazuje ekvivalenci obou výše uvedených vysvětlení.

Pokud vezmeme v úvahu první z výše uvedených formálních definic , řetězec "1011" je přijat, protože při jeho čtení může projít sekvence stavů , která splňuje podmínky 1-3. $M$ $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$
Pokud vezmeme v úvahu druhou z formálních definic, pasáž zdola nahoru ukazuje, že , tedy , a pak , odkud , a, konečně, . Protože tato sada obsahuje , je akceptován řetězec "1011". $\Delta ^{*}(p,\epsilon )=\{p\}$ ${\displaystyle \Delta ^{*}(p,1)=\Delta (p,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(str,10)=\Delta (p,0)\cup \Delta (q,0)=\{p\}\cup \{\))$ ${\displaystyle \Delta ^{*}(p,101)=\Delta (p,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(str,1011)=\Delta (p,1)\cup \Delta (q,1)=\{p,q\}\cup \{\))$ ${\displaystyle \{q\))$

Naproti tomu řetězec "10" je automatem odmítnut (všechny možné sekvence stavů pro vstupní řetězec pro daný vstup jsou zobrazeny na obrázku vpravo nahoře), protože neexistuje žádná cesta, která by po přečtení konečného stavu dosáhla konečného stavu. znak 0. Přestože stavu lze dosáhnout po přijetí prvního znaku "1", neznamená to, že vstupní řetězec "10" je přijatelný. Znamená to pouze, že vstupní řetězec "1" by byl přijatelný. $M$ $q$ $q$

Ekvivalence DFA

Za speciální druh NFA lze považovat deterministický konečný automat ( DFA ), ve kterém má přechodová funkce pro jakýkoli stav a písmena abecedy pouze jeden výsledný stav. Je tedy jasné, že jakýkoli formální jazyk , který lze rozpoznat pomocí DFA, lze rozpoznat také pomocí NFA.

Naopak pro každou NFA existuje DFA, která uznává stejný formální jazyk. DFA lze sestavit pomocí konstrukce podmnožiny .

Tento výsledek ukazuje, že NFA navzdory své velké flexibilitě nedokáže rozpoznat jazyky, které nedokáže rozpoznat žádná DFA. To je také důležité v praxi, aby bylo možné převést strukturálně jednodušší NFA na výpočetně efektivnější DFA. Pokud má však NFA n stavů, výsledná DFA může mít až 2 n stavů , což někdy činí konstrukci pro velké NFA nepraktickou.

NCA s ε-přechody

Nedeterministický konečný automat s ε-přechody (NFA-ε) je dalším zobecněním již pro NFA. Tento automat přechodové funkce může mít jako vstup prázdný řetězec ε. Přechod bez použití vstupního symbolu se nazývá ε-přechod. Ve stavovém diagramu jsou tyto přechody obvykle označeny řeckým písmenem ε. ε-přechody poskytují pohodlný způsob, jak modelovat systémy, jejichž aktuální stav není přesně znám. Pokud například modelujeme systém, jehož aktuální stav není jasný (po zpracování nějakého vstupního řetězce) a může být buď q nebo q', můžeme mezi tyto dva stavy přidat ε-přechod, čímž automat uvedeme do obou stavů na stejný čas.

Formální definice

NFA-ε je formálně reprezentován 5-tice , , který se skládá z: $(Q,\Sigma ,\Delta ,q_{0},F)$

konečná množina stavů $Q$
konečná množina vstupních znaků , nazývaná abeceda $\Sigma$
přechodové funkce $\Delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow P(Q)$
počáteční (neboli počáteční ) stav $q_{0}\in Q$
množina stavů , které jsou považovány za platné (nebo konečné ) stavy . $F$ $F\subseteq Q$

Zde znamená mocninu množiny a ε znamená prázdný řetězec. $P(Q)$ $Q$

ε-Uzavření stavu nebo množiny stavů

Pro stav označme množinu stavů dosažitelných z následujících ε-přechodů v přechodových funkcích , totiž pokud existuje taková posloupnost stavů , že: $q\in Q$ $E(q)$ $q$ $\Delta$ $p\in E(q)$ ${\displaystyle q_{1},...,q_{k))$

$q_{1}=q$ ,
$q_{i+1}\in \Delta (q_{i},\epsilon )$ pro jakékoli $1\leqslant i<k$
$q_{k}=p$ .

Sada je známá jako uzávěr ε - stavu . $E(q)$ $q$

ε-uzávěr je také definován pro množinu stavů. ε-uzavření množiny stavů, , NK-automatu je definováno jako množina stavů, kterých lze dosáhnout z prvků množiny ε-přechody. Formálně pro $P$ $P$ $P\subseteq QE(P)=\cup _{q\in P}E(q)$

Přijatelné stavy

Nechť je řetězec nad abecedou . Automat přijímá řetězec , pokud existuje sekvence stavů s následujícími podmínkami: ${\displaystyle w=a_{1}a_{2}...a_{n))$ $\Sigma$ $M$ $w$ ${\displaystyle r_{0},r_{1},...,r_{n))$ $Q$

$r_{0}\in E(q_{0})$
$r_{i+1}\in E(r')$ , kde pro jakoukoliv $r'\in \Delta (r_{i},a_{i+1})$ $i=0,...,n-1$
$r_{n}\in F$ .

Slova. První podmínka říká, že stroj začíná ze stavu, který je ze stavu dosažitelný přes ε-přechody. Druhá podmínka říká, že po přečtení stroj vybere přechod z do a následně provede libovolný počet ε-přechodů podle přechodu z do . Poslední podmínka říká, že stroj přijímá , pokud poslední vstupní znak způsobí přechod stroje do jednoho z přijatých stavů. Jinak se říká, že automat řetězec odmítne . Sada řetězců, kterou akceptuje, je jazyk , který automat rozpoznává , a tento jazyk je označen jako .

q_{0}

a_{i}

\Delta

r_{i}

r'

\Delta

r'

r_{i+1}

w

M

M

L(M)

Příklad

Nechť existuje NFA-ε s binární abecedou, která určuje, zda vstupní řetězec obsahuje sudý počet nul nebo sudý počet jedniček. Všimněte si, že 0 výskytů je sudé číslo. $M$

Ve formálním zápisu nechť , kde přechodový vztah může být definován takovou tabulkou přechodů stavů : $M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta ,S_{0} ,\{S_{1},S_{3}\})$ $\Delta$

VchodStát	0	jeden	ε
S0 _	{}	{}	{ S 1 , S 3 }
S1 _	{ S2 } _	{ S 1 }	{}
S2 _	{ S 1 }	{ S2 } _	{}
S3 _	{ S 3 }	{ S4 } _	{}
S4 _	{ S4 } _	{ S 3 }	{}

$M$ lze považovat za spojení dvou DFA , jednoho se státy a druhého se státy . Jazyk lze popsat jako regulární jazyk daný regulárním výrazem (1*(01*01*)*) ∪ (0*(10*10*)*). Definujeme pomocí ε-přechodů, ale můžeme definovat i bez nich. $\{S_{1},S_{2}\}$ $\{S_{3},S_{4}\}$ $M$ $M$ $M$

Ekvivalence NFA

Abychom ukázali, že NFA-ε je ekvivalentní NFA, nejprve poznamenejme, že NFA je speciální případ NFA-ε, zbývá ukázat, že pro jakýkoli NFA-ε existuje ekvivalent NFA.

Nechť existuje NFA-ε. NFA je ekvivalentní , kde pro libovolné a . $A=(Q,\Sigma ,\Delta ,q_{0},F)$ $A'=(Q,\Sigma ,\Delta ',E(q_{0}),F)$ $A$ $a\in\Sigma$ $q\in Q$ $\Delta '(q,a)=E(\Delta (q,a))$

Potom je NFA-ε ekvivalentní NFA. Protože NFA je ekvivalentní DFA, NFA-ε je také ekvivalentní DFA.

Vlastnosti uzávěru

Říká se, že NFA je uzavřena v rámci ( binární / unární ) operace. Pokud NFA rozpozná jazyky, které jsou získány aplikací této operace na jazyky uznané NFA. NFA jsou uzavřeny s ohledem na následující operace.

Sloučení (viz obrázek)
průsečík
Zřetězení
Přidání
Kleene uzávěr

Protože NFA jsou ekvivalentní ε-přechodovým nedeterministickým konečným automatům (NFA-ε), výše uvedené uzávěry jsou prokázány pomocí uzávěrových vlastností NFA-ε. Z výše uvedených vlastností uzavření vyplývá, že NFA rozpoznávají pouze regulární jazyky .

NFA lze sestavit z libovolného regulárního výrazu pomocí Thompsonova algoritmu .

Vlastnosti

Stroj začíná od určitého počátečního stavu a čte řetězec znaků sestávající z písmen jeho abecedy . Automat pomocí přechodové funkce Δ určí další stav z aktuálního stavu a právě přečteného znaku nebo prázdného řetězce. „Další stav NFA však závisí nejen na aktuálním vstupním symbolu, ale také na libovolném počtu následných vstupních událostí. Zatímco tyto následné události probíhají, není možné určit, v jakém stavu se stroj nachází“ [13] . Pokud je automat v konečném stavu po posledním přečteném znaku, NFA říká, že řetězec přijme, jinak se říká, že řetězec odmítne.

Sada všech řetězců akceptovaných NFA je jazyk, který NFA akceptuje. Tento jazyk je regulárním jazykem .

Pro jakýkoli NFA lze najít deterministický konečný automat (DFA), který přijímá stejný jazyk. Proto je možné převést existující NFA na DFA za účelem implementace (možná) jednoduššího stroje. Taková transformace se provádí pomocí konstrukce podmnožiny , což může vést k exponenciálnímu nárůstu počtu požadovaných stavů. Formální důkaz konstrukce podmnožiny naleznete v článku " Konstrukce podmnožiny ".

Implementace

NFA lze modelovat jedním z následujících způsobů:

Převést na ekvivalentní DFA. V některých případech to může vést k explozivnímu nárůstu počtu stavů [14] .
Udržování množiny všech stavů, ve kterých se NFA může po přečtení slova nacházet. Při zpracování vstupního symbolu je nutné zkombinovat výsledky přechodové funkce aplikované na aktuální sadu stavů a získat tak další sadu. Pokud jsou povoleny ε-přechody, je třeba zahrnout také všechny stavy dosažitelné přes takové přechody (ε-uzavření). Každý krok vyžaduje maximálně výpočty, kde s je počet stavů NFA. Automat přijímá řetězec právě tehdy, když je při zpracování posledního vstupního znaku jeden z aktuálních stavů konečný. Řetězec délky n lze zpracovat v čase O (ns 2 ) [15] pomocí paměti O ( s ). $s^{2}$

Aplikace NCA

NFA a DFA jsou ekvivalentní v tom smyslu, že pokud je jazyk rozpoznán NFA automatem, rozpozná jej také DFA. Opak je také pravdou. Stanovení takové ekvivalence je důležité a užitečné. Důležité, protože NFA mohou být použity ke snížení složitosti matematické práce, která je potřebná k vytvoření důležitých vlastností v teorii algoritmů . Například je mnohem snazší prokázat uzavřenost běžných jazyků pomocí NFA než pomocí DFA. Užitečné, protože sestavení NFA pro rozpoznání daného jazyka je někdy mnohem důležitější než vytvoření DFA pro tento jazyk.

Viz také

Deterministický stavový automat
Dvoucestný nedeterministický konečný stroj
Automatická s pamětí zásobníku
Turingův stroj

Poznámky

↑ Martin, 2010 , str. 108.
↑ Rabin a Scott, 1959 , s. 114–125.
↑ Volební sekvence může vést k "slepé uličce", ve které žádný z přechodů není platný pro aktuální vstupní symbol a tento případ je považován za selhání (řetězec je odmítnut).
↑ Hopcroft, Ullman, 1979 , str. 19.
↑ Aho, Hopcroft & Ullman 1974 , str. 319.
↑ Hopcroft, Ullman, 1979 , str. 19-20.
↑ Sipser, 1997 , str. 48.
↑ Hopcroft, Motwani, Ullman, 2001 , str. 56.
↑ Aho, Hopcroft & Ullman 1974 , str. 320.
↑ Sipser, 1997 , str. 54.
↑ Hopcroft, Ullman, 1979 , str. 21.
↑ Hopcroft, Motwani, Ullman, 2001 , str. 59.
↑ Finite-State Machine FOLDOC Free Online Dictionary of Computing . Datum přístupu: 11. února 2020. Archivováno z originálu 4. dubna 2015. (neurčitý)
↑ Chris Calabro. NFA do DFA vybuchnout. 2005-02-27 . Staženo 11. února 2020. Archivováno z originálu 7. února 2013. (neurčitý)
↑ Hopcroft, Motwani, Ullman, 2001 , str. 153.

Literatura

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Návrh a analýza počítačových algoritmů . - Reading/MA: Addison-Wesley, 1974. - ISBN 0-201-00029-6 .
- Aho A., Hopcroft J., Ulman J. Konstrukce a analýza výpočetních algoritmů. - Moskva: Mir, 1979.
John E. Hopcroft, Jeffrey D. Ullman. Úvod do teorie automatů, jazyků a počítání . - Reading/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Úvod do teorie automatů, jazyků a počítání . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .
Michael Sipser. Úvod do teorie počítání . - Boston/MA: PWS Publishing Co., 1997. - ISBN 0-534-94728-X .
John Martin. Úvod do jazyků a teorie počítání. - McGraw Hill, 2010. - ISBN 978-0071289429 .
Rabin MO, Scott D. Konečné automaty a jejich rozhodovací problémy // IBM Journal of Research and Development. - 1959. - Duben ( díl 3 , číslo 2 ). - doi : 10.1147/rd.32.0114 .
Allan C., Avgustinov P., Christensen AS, Hendren L., Kuzins S., Lhoták O., de Moor O., Sereni D., Sittampalam G., Tibble J. Adding trace matching with free variables to AspectJ // In Sborník příspěvků z 20. výroční konference ACM SIGPLAN o objektově orientovaném programování, systémech, jazycích a aplikacích . — San Diego, CA, USA: OOPSLA '05. ACM, New York, NY, 2005. s. 345-364. Archivováno 18. září 2009 na Wayback Machine

Formální jazyky a formální gramatiky
Obecné pojmy	Chomského hierarchie Abeceda Slovo
Typ 0	Neomezená gramatika Turingův stroj výčtový jazyk Řešitelný jazyk
Typ 1	Kontextově citlivá gramatika Kontextový jazyk Lineárně ohraničený automat
Typ 2	Bezkontextová gramatika Nejednoznačná gramatika Bezkontextový jazyk Zásobníkový automat ( deterministický ) Růstové lemma Ogdenovo lemma Cookova věta
Typ 3	Pravidelná gramatika regulární jazyk Regulární výraz Stavový stroj ( deterministický , nedeterministický ) Minimalizace DFA Stanovení NFA Myhillova-Nerodova věta
rozebrat	LL analyzátor LR analyzátor Metoda rekurzivního sestupu Kok-Younger-Kasami algoritmus