Ikke-deterministisk tilstandsmaskine

En ikke-deterministisk finit automat (NFA, eng. nondeterministic finite automaton , NFA) er en deterministisk finite automat (DFA, eng. deterministic finite automaton , DFA), der ikke opfylder følgende betingelser:

enhver af dens overgange er entydigt bestemt af den aktuelle tilstand og inputsymbolet
læsning af et inputtegn er påkrævet for hver tilstandsændring.

Især er enhver DFA også en NFA.

Ved at bruge undersætkonstruktionsalgoritmen , kan enhver NFA konverteres til en ækvivalent DFA, det vil sige en DFA, der genkender det samme formelle sprog [1] . Ligesom DFA genkender NFA kun almindelige sprog .

NFA blev foreslået i 1959 af Michael O. Rabin og Dana Scott [2] som viste, at det svarede til DFA. NFA bruges i implementeringen af regulære udtryk - Thompsons konstruktion er en algoritme til at konvertere et regulært udtryk til NFA, der effektivt kan genkende mønstret af strenge. Omvendt kan Kleenes algoritme bruges til at transformere en NFA til et regulært udtryk, hvis størrelse generelt afhænger eksponentielt af størrelsen af automaten.

NFA er generaliseret på mange måder, for eksempel: ikke-deterministiske endelige automater med ε-overgange , finite-state transducere, pushdown- automater , alternerende automater, ω-automater og probabilistiske automater . Ud over DFA kendes andre specielle tilfælde af NFA'er - entydige finite automata ( eng. unambiguous finite automata , UFA) og self -verifying finite automata ( eng. self-verifying finite automata , SVFA).

Uformel introduktion

Der er flere uformelle tilsvarende beskrivelser:

En NFA tager ligesom en DFA en streng af inputtegn. For hvert inputsymbol går det over til en ny tilstand, indtil det har behandlet alle inputsymboler. Ved hvert trin vælger automaten tilfældigt en af de mulige overgange. Hvis der er et "forhåbentlig pass", det vil sige en sekvens af valg, der fører til en endelig tilstand, efter at inputstrengen er fuldt ud hentet, så accepteres strengen. Hvis der ikke er nogen sekvens, der efter at have behandlet hele inputstrengen [3] bringer automaten til den endelige tilstand, så afvises inputstrengen [4] [5] .
Lad NFA igen tage en streng af inputtegn, det ene tegn efter det andet. Ved hvert trin, hvor to eller flere overgange viser sig at være gyldige, "kloner" automaten sig selv til det nødvendige antal kopier, som hver især laver forskellige overgange. Hvis ingen overgang kan foretages, er den aktuelle kopi en blindgyde og dør. Hvis nogen af kopierne efter at have hentet alle tegn fra inputstrengen går til den endelige tilstand, accepteres inputstrengen, ellers afvises den [6] [7] [8] .

Formel definition

For en mere elementær introduktion til den formelle definition, se artiklen " Automata Theory ".

Automater

En NFA er formelt repræsenteret som en 5-tuple bestående af: $(Q,\Sigma,\Delta,q_{0},F)$

endeligt sæt af tilstande . $Q$
endeligt sæt af inputsymboler . $\Sigma$
overgangsfunktioner :. _ $\Delta$ $Q\time \Sigma \rightarrow P(Q)$
initial tilstand . $q_{0}\in Q$
sæt af tilstande, der kan genkendes som sluttilstande . $F$ $F\subseteq Q$

Her menes graden af sættet . $P(Q)$ $Q$

Genkendt sprog

Givet en NFA , genkender den et sprog, der er betegnet som og defineret som sættet af alle strenge over alfabetet , der accepteres af automaten . $M=(Q,\Sigma,\Delta,q_{0},F)$ $L(M)$ $\Sigma$ $M$

Generelt set er der ifølge de uformelle forklaringer ovenfor flere ækvivalente formelle strengdefinitioner, der accepteres af automaten : ${\displaystyle w=a_{1}a_{2}...a_{n))$ $M$

$w$ accepteres, hvis der er en sekvens af tilstande i sådan ${\displaystyle r_{0},r_{1},...,r_{n))$ $Q$
1. $r_{0}=q_{0}$
2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$ , til $i=0,\ldots ,n-1$
3. $r_{n}\in F$ .

Ord. Den første betingelse siger, at maskinen starter fra staten . Den anden betingelse siger, at for hvert tegn i strengen , skifter maskinen fra tilstand til tilstand i henhold til overgangsfunktionen . Den sidste betingelse siger, at maskinen accepterer en streng, hvis inputstrengen får maskinen til at afslutte i sin endelige tilstand. For at en streng skal accepteres af en automat , kræves det ikke, at nogen sekvens af tilstande ender i en endelig tilstand, det er nok, at en sekvens fører til en sådan tilstand. Ellers, dvs. hvis det er umuligt at gå fra til tilstanden fra , efter , siges automaten at afvise strengen. Det sæt af strenge, som automaten accepterer, er et sprog , der genkendes af automaten , og dette sprog betegnes som [9] [10] .

q_{0}

w

\Delta

w

w

w

M

q_{0}

F

w

M

M

L(M)

Alternativt accepteres det, hvis , hvor er defineret rekursivt : $w$ $\Delta ^{*}(q_{0},w)\cap F\not =\emptyset$ $\Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)$
1. ${\displaystyle \Delta ^{*}(r,\epsilon )=\{r\))$ , hvor er den tomme streng $\epsilon$
2. $\Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)$ for enhver . $x\in \Sigma ^{*},a\in \Sigma$

Med andre ord, er sættet af alle tilstande tilgængeligt fra staten, når strengen hentes . En streng accepteres, hvis en eller anden sluttilstand fra kan nås fra starttilstanden for inputstrengen [11] [12] .

\Delta ^{*}(r,x)

r

x

w

F

q_{0}

w

Oprindelig tilstand

Automatdefinitionen ovenfor bruger en enkelt starttilstand , hvilket ikke er et krav. Nogle gange er en NFA defineret med et sæt begyndelsestilstande. Der er en simpel konstruktion , der tager en NFA med flere starttilstande til en NFA med en enkelt starttilstand.

Eksempel

Den følgende binære alfabetautomat bestemmer, om inputstrengen ender på én. Lad , hvor overgangsfunktionen kan defineres af følgende tilstandsovergangstabel (sammenlign med den øverste figur til venstre): $M$ $M=(\{p,q\},\{0,1\},\Delta ,p,\{q\})$ $\Delta$

IndgangStat	0	en
$s$	${\displaystyle \{p\))$	${\displaystyle \{p,q\))$
$q$	$\tomt sæt$	$\tomt sæt$

Da sættet indeholder mere end én tilstand, er automaten ikke-deterministisk. Automatsproget kan beskrives som et regulært sprog givet af et regulært udtryk . $\Delta(p,1)$ $M$ $M$ (0|1)*1

Alle mulige tilstandssekvenser for inputstrengen "1011" er vist i figuren nedenfor. Strengen accepteres af automaten , fordi en af tilstandssekvenserne opfylder ovenstående definition. Det gør ikke noget, at de andre sekvenser ikke lykkes. Tegningen kan fortolkes på to måder: $M$

Med hensyn til "lucky run"-forklaringen ovenfor repræsenterer hver sti i figuren en sekvens af valg . $M$
For at forklare i termer af "kloning", viser hver lodret kolonne alle klonerne af automaten på et givet tidspunkt, flere pile, der kommer ud af en knude, betyder kloning, en knude uden udgående pile betyder "død" af klonen. $M$

Evnen til at læse den samme figur på to måder viser også ækvivalensen af de to forklaringer ovenfor.

Hvis vi betragter den første af de formelle definitioner ovenfor , accepteres strengen "1011", for når den læses , kan en sekvens af tilstande gå igennem , der opfylder betingelserne 1-3. $M$ $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$
Hvis vi betragter den anden af de formelle definitioner, viser passagen nedefra og op, at derfor, , og derefter , hvorfra , og til sidst, . Da dette sæt indeholder , accepteres strengen "1011". $\Delta ^{*}(p,\epsilon )=\{p\}$ ${\displaystyle \Delta ^{*}(p,1)=\Delta (p,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(s,10)=\Delta (s,0)\kop \Delta (q,0)=\{p\}\kop \{\))$ ${\displaystyle \Delta ^{*}(s,101)=\Delta (s,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(s,1011)=\Delta (s,1)\kop \Delta (q,1)=\{p,q\}\kop \{\))$ ${\displaystyle \{q\))$

I modsætning hertil afvises strengen "10" af automaten (alle mulige sekvenser af tilstande for inputstrengen for en given input er vist i figuren øverst til højre), da der ikke er nogen sti, der når den endelige tilstand efter at have læst den endelige tegn 0. Selvom tilstanden kan nås efter at have modtaget det første tegn "1", betyder det ikke, at inputstrengen "10" er acceptabel. Det betyder kun, at inputstrengen "1" ville være acceptabel. $M$ $q$ $q$

DFA-ækvivalens

En deterministisk endelig automat ( DFA ) kan betragtes som en speciel slags NFA, hvor overgangsfunktionen for enhver tilstand og bogstaver i alfabetet kun har én resulterende tilstand. Det er således klart, at ethvert formelt sprog , der kan genkendes med en DFA, også kan genkendes med en NFA.

Omvendt er der for enhver NFA en DFA, der genkender det samme formelle sprog. En DFA kan bygges ved hjælp af undersætkonstruktionen .

Dette resultat viser, at NFA på trods af sin store fleksibilitet ikke er i stand til at genkende sprog, der ikke kan genkendes af nogen DFA. Dette er også vigtigt i praksis for at konvertere strukturelt enklere NFA'er til mere beregningseffektive DFA'er. Men hvis NFA har n tilstande, kan den resulterende DFA have op til 2n tilstande, hvilket nogle gange gør konstruktionen upraktisk for store NFA'er.

NCA med ε-overgange

Den ikke-deterministiske endelige automat med ε-overgange (NFA-ε) er en yderligere generalisering allerede for NFA. Denne overgangsfunktionsautomat har lov til at have den tomme streng ε som input. En overgang uden brug af et inputsymbol kaldes en ε-overgang. I et tilstandsdiagram er disse overgange normalt mærket med det græske bogstav ε. ε-overgange giver en bekvem måde at modellere systemer, hvis nuværende tilstand ikke er nøjagtigt kendt. For eksempel, hvis vi modellerer et system, hvis nuværende tilstand ikke er klar (efter at have behandlet en inputstreng) og kan være enten q eller q', kan vi tilføje en ε-overgang mellem disse to tilstande, hvilket bringer automaten til begge tilstande kl. den samme tid.

Formel definition

NFA-ε er formelt repræsenteret af en 5-tupel , , som består af: $(Q,\Sigma,\Delta,q_{0},F)$

endeligt sæt af tilstande $Q$
et begrænset sæt af inputtegn , kaldet alfabetet $\Sigma$
overgangsfunktioner _ $\Delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow P(Q)$
initial (eller start ) tilstand $q_{0}\in Q$
et sæt tilstande , der betragtes som gyldige (eller endelige ) tilstande . $F$ $F\subseteq Q$

Her betyder sættets magt , og ε betyder den tomme streng. $P(Q)$ $Q$

ε-Lukning af en tilstand eller et sæt af tilstande

For en tilstand, lad betegne det sæt af tilstande, der kan nås fra følgende ε-overgange i overgangsfunktionerne , nemlig hvis der er en sekvens af tilstande, således at: $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 )$ for enhver $1\leqslant i<k$
$q_{k}=p$ .

Sættet er kendt som ε -tilstandslukningen . $E(q)$ $q$

ε-lukningen er også defineret for sættet af tilstande. ε-lukningen af sættet af tilstande, , af NK-automaten er defineret som det sæt af tilstande, der kan nås fra sættets elementer ved ε-overgange. Formelt, for $P$ $P$ $P\subseteq QE(P)=\cup _{q\in P}E(q)$

Acceptable tilstande

Lad være en snor over alfabetet . Automaten accepterer en streng, hvis der er en sekvens af tilstande i med følgende betingelser: ${\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')$ , hvor for evt $r'\in \Delta (r_{i},a_{i+1})$ $i=0,...,n-1$
$r_{n}\in F$ .

Ord. Den første betingelse siger, at maskinen starter fra en tilstand, der er tilgængelig fra tilstanden via ε-overgange. Den anden betingelse siger, at efter læsning vælger maskinen overgangen fra til og udfører derefter et vilkårligt antal ε-overgange i henhold til overgangen fra til . Den sidste betingelse siger, at maskinen accepterer, hvis det sidste inputtegn får maskinen til at skifte til en af de accepterede tilstande. Ellers siges automaten at afvise strengen. Det sæt af strenge, den accepterer, er det sprog , som automaten genkender , og dette sprog betegnes som .

q_{0}

a_{i}

\Delta

r_{i}

r'

\Delta

r'

r_{i+1}

w

M

M

L(M)

Eksempel

Lad der være en NFA-ε med et binært alfabet, der bestemmer, om inputstrengen indeholder et lige antal nuller eller et lige antal enere. Bemærk, at 0 forekomster er et lige tal. $M$

I formel notation, lad , hvor overgangsrelationen kan defineres af en sådan tilstandsovergangstabel : $M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta ,S_{0} ,\{S_{1},S_{3}\})$ $\Delta$

IndgangStat	0	en	ε
S0 _	{}	{}	{ S 1 , S 3 }
S1 _	{ S2 } _	{ S 1 }	{}
S2 _	{ S 1 }	{ S2 } _	{}
S3 _	{ S 3 }	{ S4 } _	{}
S4 _	{ S4 } _	{ S 3 }	{}

$M$ kan opfattes som en forening af to DFA'er , den ene med stater og den anden med stater . Sproget kan beskrives som et regulært sprog givet af det regulære udtryk (1*(01*01*)*) ∪ (0*(10*10*)*). Vi definerer ved hjælp af ε-overgange, men vi kan definere uden dem. $\{S_{1},S_{2}\}$ $\{S_{3},S_{4}\}$ $M$ $M$ $M$

Ækvivalens af NFA'er

For at vise, at NFA-ε er ækvivalent med NFA, skal man først bemærke, at NFA er et specialtilfælde af NFA-ε, det er tilbage at vise, at der for enhver NFA-ε er en tilsvarende NFA.

Lad der være NFA-ε. NFA svarer til , hvor for enhver og . $A=(Q,\Sigma,\Delta,q_{0},F)$ $A'=(Q,\Sigma,\Delta ',E(q_{0}),F)$ $EN$ $a\in\Sigma$ $q\in Q$ $\Delta '(q,a)=E(\Delta (q,a))$

Så svarer NFA-ε til NFA. Da NFA svarer til DFA, svarer NFA-ε også til DFA.

Lukningsegenskaber

En NFA siges at være lukket under en ( binær / unær ) operation. Hvis NFA genkender de sprog, der opnås ved at anvende denne handling på de sprog, der er anerkendt af NFA. NFA'er er lukket med hensyn til følgende operationer.

Sammenlægning (se billede)
vejkryds
Sammenkædning
Tilføjelse
Kleene lukning

Da NFA'er er ækvivalente med ε-transition nondeterministic finite automata (NFA-ε), er lukningerne ovenfor bevist ved hjælp af lukkeegenskaberne for NFA-ε. Det følger af lukningsegenskaberne ovenfor, at NFA'er kun genkender regulære sprog .

NFA'er kan bygges ud fra ethvert regulært udtryk ved hjælp af Thompson-algoritmen .

Egenskaber

Maskinen starter fra en bestemt begyndelsestilstand og læser en tegnstreng bestående af bogstaverne i dens alfabet . Automaten bruger overgangsfunktionen Δ til at bestemme den næste tilstand ud fra den aktuelle tilstand og det tegn eller den tomme streng, der lige er blevet læst. Men "NFA's næste tilstand afhænger ikke kun af det aktuelle inputsymbol, men også af et vilkårligt antal efterfølgende inputhændelser. Mens disse efterfølgende begivenheder finder sted, er det umuligt at afgøre, hvilken tilstand maskinen er i” [13] . Hvis automaten er i den endelige tilstand efter det sidst læste tegn, siges NFA at acceptere strengen, ellers siges den at afvise strengen.

Sættet af alle strenge, der accepteres af NFA, er det sprog, som NFA accepterer. Dette sprog er et almindeligt sprog .

For enhver NFA kan man finde en deterministisk finit automat (DFA), der accepterer det samme sprog. Derfor er det muligt at konvertere en eksisterende NFA til en DFA for at implementere en (evt.) enklere maskine. En sådan transformation udføres ved hjælp af delmængdekonstruktionen , hvilket kan føre til en eksponentiel stigning i antallet af påkrævede tilstande. For et formelt bevis for delmængdekonstruktionen, se artiklen " Undersætkonstruktion [ ".

Implementering

NFA kan modelleres på en af følgende måder:

Konverter til tilsvarende DFA. I nogle tilfælde kan dette føre til en eksplosiv vækst i antallet af stater [14] .
Vedligeholdelse af sættet af alle stater, som NFA kan befinde sig i efter at have læst ordet. Når et inputsymbol behandles, er det nødvendigt at kombinere resultaterne af overgangsfunktionen anvendt på det aktuelle sæt af tilstande for at få det næste sæt. Hvis ε-overgange er tilladt, skal man også inkludere alle tilstande, der kan nås via sådanne overgange (ε-lukning). Hvert trin kræver højst beregninger, hvor s er antallet af NFA-stater. Automaten accepterer en streng, hvis og kun hvis en af de aktuelle tilstande er endelige ved behandling af det sidste inputtegn. En streng med længden n kan behandles i O (ns 2 ) tid [15] ved hjælp af O ( s ) hukommelse. $s^{2}$

NCA Applications

NFA og DFA er ækvivalente i den forstand, at hvis et sprog genkendes af en NFA af en automat, genkendes det også af en DFA. Det omvendte er også sandt. Det er vigtigt og nyttigt at etablere en sådan ækvivalens. Vigtigt, fordi NFA'er kan bruges til at reducere kompleksiteten af det matematiske arbejde, der er nødvendigt for at etablere vigtige egenskaber i algoritmeteori . For eksempel er det meget lettere at bevise lukketheden af regulære sprog med NFA'er end med DFA'er. Nyttigt, fordi det at opbygge en NFA for at anerkende, at sprog nogle gange er meget vigtigere end at bygge en DFA for det sprog.

Se også

Deterministisk tilstandsmaskine
To-vejs ikke-deterministisk endelig maskine
Automatisk med magasinhukommelse
Turing maskine

Noter

↑ Martin, 2010 , s. 108.
↑ Rabin og Scott, 1959 , s. 114-125.
↑ En valgsekvens kan føre til en "blindgyde", hvor ingen af overgangene er gyldige for det aktuelle inputsymbol, og denne sag betragtes som en fiasko (strengen afvises).
↑ Hopcroft, Ullman, 1979 , s. 19.
↑ Aho, Hopcroft & Ullman 1974 , s. 319.
↑ Hopcroft, Ullman, 1979 , s. 19-20.
↑ Sipser, 1997 , s. 48.
↑ Hopcroft, Motwani, Ullman, 2001 , s. 56.
↑ Aho, Hopcroft & Ullman 1974 , s. 320.
↑ Sipser, 1997 , s. 54.
↑ Hopcroft, Ullman, 1979 , s. 21.
↑ Hopcroft, Motwani, Ullman, 2001 , s. 59.
↑ Finite-State Machine FOLDOC Free Online Dictionary of Computing . Dato for adgang: 11. februar 2020. Arkiveret fra originalen den 4. april 2015. (ubestemt)
↑ Chris Calabro. NFA til DFA sprænges. 2005-02-27 . Hentet 11. februar 2020. Arkiveret fra originalen 7. februar 2013. (ubestemt)
↑ Hopcroft, Motwani, Ullman, 2001 , s. 153.

Litteratur

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Design og analyse af computeralgoritmer . - Læsning/MA: Addison-Wesley, 1974. - ISBN 0-201-00029-6 .
- Aho A., Hopcroft J., Ulman J. Konstruktion og analyse af beregningsalgoritmer. - Moskva: Mir, 1979.
John E. Hopcroft, Jeffrey D. Ullman. Introduktion til automatteori, sprog og beregning . - Læsning/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Introduktion til automatteori, sprog og beregning . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .
Michael Sipser. Introduktion til teorien om beregning . - Boston/MA: PWS Publishing Co., 1997. - ISBN 0-534-94728-X .
John Martin. Introduktion til sprog og teorien om beregning. - McGraw Hill, 2010. - ISBN 978-0071289429 .
Rabin MO, Scott D. Finite Automata og deres beslutningsproblemer // IBM Journal of Research and Development. - 1959. - April ( bind 3 , hæfte 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 Proceedings fra den 20. årlige ACM SIGPLAN-konference om objektorienteret programmering, systemer, sprog og applikationer . — San Diego, Californien, USA: OOPSLA '05. ACM, New York, NY, 2005. s. 345-364. Arkiveret 18. september 2009 på Wayback Machine

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme