Icke-deterministisk tillståndsmaskin

En icke-deterministisk finit automat (NFA, eng. nondeterministic finite automaton , NFA) är en deterministisk finit automat (DFA, eng. deterministic finite automaton , DFA) som inte uppfyller följande villkor:

någon av dess övergångar bestäms unikt av det aktuella tillståndet och ingångssymbolen
läsning av ett inmatningstecken krävs för varje tillståndsändring.

I synnerhet är alla DFA också en NFA.

Med hjälp av subset-konstruktionsalgoritmen , kan vilken NFA som helst konverteras till en likvärdig DFA, det vill säga en DFA som känner igen samma formella språk [1] . Precis som DFA känner NFA bara igen vanliga språk .

NFA föreslogs 1959 av Michael O. Rabin och Dana Scott [2] som visade att det var likvärdigt med DFA. NFA används vid implementering av reguljära uttryck - Thompsons konstruktion är en algoritm för att konvertera ett reguljärt uttryck till NFA som effektivt kan känna igen mönstret av strängar. Omvänt kan Kleenes algoritm användas för att omvandla en NFA till ett reguljärt uttryck vars storlek i allmänhet beror exponentiellt på storleken på automaten.

NFA är generaliserat på många sätt, till exempel: icke-deterministiska finita automater med ε-övergångar , finita-tillståndsgivare, pushdown- automater , alternerande automater, ω-automater och probabilistiska automater . Förutom DFA är andra specialfall av NFA kända - entydiga finite automata ( eng. entydiga finite automata , UFA) och självverifierande finita automater ( eng. self-verifying finite automata , SVFA).

Informell introduktion

Det finns flera informella likvärdiga beskrivningar:

En NFA, som en DFA , tar en sträng av inmatade tecken. För varje ingångssymbol övergår den till ett nytt tillstånd tills den har bearbetat alla inmatningssymboler. Vid varje steg väljer automaten slumpmässigt en av de möjliga övergångarna. Om det finns ett "hoppfullt pass", det vill säga någon sekvens av val som leder till ett slutligt tillstånd efter att inmatningssträngen har hämtats helt, då accepteras strängen. Om det inte finns någon sekvens som, efter att ha bearbetat hela inmatningssträngen [3] , för automaten till det slutliga tillståndet, då avvisas inmatningssträngen [4] [5] .
Låt NFA återigen ta en rad inmatade tecken, ett tecken efter det andra. Vid varje steg där två eller flera övergångar visar sig vara giltiga "klonar" automaten sig själv till det antal kopior som krävs, som var och en gör olika övergångar. Om ingen övergång kan göras är den aktuella kopian en återvändsgränd och dör. Om, efter att ha hämtat alla tecken från inmatningssträngen, någon av kopiorna går till det slutliga tillståndet, accepteras inmatningssträngen, annars avvisas den [6] [7] [8] .

Formell definition

För en mer elementär introduktion till den formella definitionen, se artikeln " Automatateory ".

Automatisera

En NFA representeras formellt som en 5-tupel bestående av: $(Q,\Sigma,\Delta,q_{0},F)$

ändlig uppsättning tillstånd . $F$
ändlig uppsättning ingångssymboler . $\Sigma$
övergångsfunktioner : . $\Delta$ $Q\times \Sigma \rightarrow P(Q)$
initialtillstånd . _ $q_{0}\in Q$
uppsättningar av tillstånd som kan kännas igen som sluttillstånd . $F$ $F\subseteq Q$

Här menas graden av uppsättningen . $P(Q)$ $F$

Känt språk

Med en NFA känner den igen ett språk som betecknas som och definieras som uppsättningen av alla strängar över alfabetet som accepteras av automaten . $M=(Q,\Sigma,\Delta,q_{0},F)$ $L(M)$ $\Sigma$ $M$

I allmänna termer, enligt de informella förklaringarna ovan , finns det flera likvärdiga formella strängdefinitioner som accepteras av automaten : ${\displaystyle w=a_{1}a_{2}...a_{n))$ $M$

$w$ accepteras om det finns en sekvens av tillstånd i sådan ${\displaystyle r_{0},r_{1},...,r_{n))$ $F$
1. $r_{0}=q_{0}$
2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$ , för $i=0,\ldots ,n-1$
3. $r_{n}\in F$ .

Ord. Det första villkoret säger att maskinen startar från staten . Det andra villkoret säger att för varje tecken i strängen övergår maskinen från tillstånd till tillstånd enligt övergångsfunktionen . Det sista villkoret säger att maskinen accepterar en sträng om inmatningssträngen får maskinen att avslutas i sitt slutliga tillstånd. För att en sträng ska accepteras av en automat krävs det inte att någon sekvens av tillstånd slutar i ett sluttillstånd, det räcker att en sekvens leder till ett sådant tillstånd. Annars, d.v.s. om det är omöjligt att gå från till tillståndet från , efter , sägs automaten avvisa strängen. Uppsättningen strängar som automaten accepterar är ett språk som känns igen av automaten , och detta språk betecknas som [9] [10] .

q_{0}

w

\Delta

w

w

w

M

q_{0}

F

w

M

M

L(M)

Alternativt accepteras det om , där definieras rekursivt : $w$ $\Delta ^{*}(q_{0},w)\cap F\not =\emptyset$ $\Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)$
1. ${\displaystyle \Delta ^{*}(r,\epsilon )=\{r\))$ , var är den tomma strängen $\epsilon$
2. $\Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)$ för någon . $x\in \Sigma ^{*},a\in \Sigma$

Med andra ord, är uppsättningen av alla tillstånd nåbar från staten när strängen hämtas . En sträng accepteras om något sluttillstånd från kan nås från starttillståndet för ingångssträngen [11] [12] .

\Delta ^{*}(r,x)

r

x

w

F

q_{0}

w

Initialt tillstånd

Automatdefinitionen ovan använder ett enda initialtillstånd , vilket inte är ett krav. Ibland definieras en NFA med en uppsättning initiala tillstånd. Det finns en enkel konstruktion som tar en NFA med flera initiala tillstånd till en NFA med ett enda initialtillstånd.

Exempel

Följande binära alfabetautomat bestämmer om inmatningssträngen slutar på ett. Låt , där övergångsfunktionen kan definieras av följande tillståndsövergångstabell (jämför med den övre bilden till vänster): $M$ $M=(\{p,q\},\{0,1\},\Delta ,p,\{q\})$ $\Delta$

Ingångstat	0	ett
$sid$	${\displaystyle \{p\))$	${\displaystyle \{p,q\))$
$q$	$\emptyset$	$\emptyset$

Eftersom uppsättningen innehåller mer än ett tillstånd är automaten icke-deterministisk. Automatspråket kan beskrivas som ett reguljärt språk som ges av ett reguljärt uttryck . $\Delta(s,1)$ $M$ $M$ (0|1)*1

Alla möjliga tillståndssekvenser för ingångssträngen "1011" visas i figuren nedan. Strängen accepteras av automaten eftersom en av tillståndssekvenserna uppfyller ovanstående definition. Det spelar ingen roll att de andra sekvenserna inte lyckas. Ritningen kan tolkas på två sätt: $M$

När det gäller "lyckoloppet"-förklaringen ovan representerar varje väg i figuren en sekvens av val . $M$
För att förklara i termer av "kloning", visar varje vertikal kolumn alla kloner av automaten vid en given tidpunkt, flera pilar som kommer ut från en nod betyder kloning, en nod utan utgående pilar betyder "död" för klonen. $M$

Förmågan att läsa samma figur på två sätt visar också motsvarigheten mellan de två förklaringarna ovan.

Om vi betraktar den första av de formella definitionerna ovan accepteras strängen "1011", för när den läses kan en sekvens av tillstånd gå igenom som uppfyller villkoren 1-3. $M$ $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$
Om vi betraktar den andra av de formella definitionerna, visar passagen nerifrån och upp att , därför , och sedan , varifrån , och slutligen . Eftersom denna uppsättning innehåller accepteras strängen "1011". $\Delta ^{*}(p,\epsilon )=\{p\}$ ${\displaystyle \Delta ^{*}(p,1)=\Delta (s,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(s,10)=\Delta (s,0)\cup \Delta (q,0)=\{p\}\cup \{\))$ ${\displaystyle \Delta ^{*}(s,101)=\Delta (s,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(s,1011)=\Delta (s,1)\cup \Delta (q,1)=\{p,q\}\cup \{\))$ $\{q\}$

Däremot avvisas strängen "10" av automaten (alla möjliga sekvenser av tillstånd för ingångssträngen för en given ingång visas i den övre högra figuren), eftersom det inte finns någon väg som når det slutliga tillståndet efter att ha läst den slutliga tecken 0. Även om tillståndet kan nås efter att ha mottagit det första tecknet "1" betyder det inte att inmatningssträngen "10" är acceptabel. Det betyder bara att inmatningssträngen "1" skulle vara acceptabel. $M$ $q$ $q$

DFA-ekvivalens

En deterministisk finit automat ( DFA ) kan betraktas som en speciell typ av NFA där övergångsfunktionen för alla tillstånd och bokstäver i alfabetet endast har ett resulterande tillstånd. Således är det tydligt att vilket formellt språk som helst som kan kännas igen med en DFA också kan kännas igen med en NFA.

Omvänt, för alla NFA finns det en DFA som känner igen samma formella språk. En DFA kan byggas med hjälp av delmängdskonstruktionen .

Detta resultat visar att NFA, trots sin stora flexibilitet, inte kan känna igen språk som inte kan kännas igen av någon DFA. Detta är också viktigt i praktiken för att konvertera strukturellt enklare NFA:er till mer beräkningseffektiva DFA:er. Men om NFA har n tillstånd kan den resulterande DFA ha upp till 2n tillstånd, vilket ibland gör konstruktionen opraktisk för stora NFA.

NCA med ε-övergångar

Den icke-deterministiska finita automaten med ε-övergångar (NFA-ε) är en ytterligare generalisering redan för NFA. Denna övergångsfunktionsautomat får ha den tomma strängen ε som indata. En övergång utan att använda en ingångssymbol kallas en ε-övergång. I ett tillståndsdiagram är dessa övergångar vanligtvis märkta med den grekiska bokstaven ε. ε-övergångar ger ett bekvämt sätt att modellera system vars nuvarande tillstånd inte är exakt känt. Till exempel, om vi modellerar ett system vars nuvarande tillstånd inte är klart (efter bearbetning av någon indatasträng) och kan vara antingen q eller q', kan vi lägga till en ε-övergång mellan dessa två tillstånd, vilket för automaten till båda tillstånden vid samtidigt.

Formell definition

NFA-ε representeras formellt av en 5-tupel , , som består av: $(Q,\Sigma,\Delta,q_{0},F)$

ändlig uppsättning tillstånd $F$
en ändlig uppsättning indatatecken , som kallas alfabetet $\Sigma$
övergångsfunktioner _ $\Delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow P(Q)$
initialtillstånd (eller starttillstånd ). $q_{0}\in Q$
en uppsättning tillstånd som anses vara giltiga (eller slutliga ) tillstånd . $F$ $F\subseteq Q$

Här betyder mängden kraft och ε betyder den tomma strängen . $P(Q)$ $F$

ε-Stängning av ett tillstånd eller en uppsättning tillstånd

För ett tillstånd, låt beteckna uppsättningen tillstånd som kan nås från följande ε-övergångar i övergångsfunktionerna , nämligen om det finns en sekvens av tillstånd så att: $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 )$ för alla $1\leqslant i<k$
$q_{k}=p$ .

Uppsättningen är känd som ε- state closure . $E(q)$ $q$

ε-förslutningen definieras också för uppsättningen av tillstånd. ε-stängningen av uppsättningen av tillstånd, , av NK-automaten definieras som den uppsättning tillstånd som kan nås från elementen i uppsättningen genom ε-övergångar. Formellt, för $P$ $P$ $P\subseteq QE(P)=\cup _{q\in P}E(q)$

Godkända tillstånd

Låt vara en sträng över alfabetet . Automaten accepterar en sträng om det finns en sekvens av tillstånd med följande villkor: ${\displaystyle w=a_{1}a_{2}...a_{n))$ $\Sigma$ $M$ $w$ ${\displaystyle r_{0},r_{1},...,r_{n))$ $F$

$r_{0}\in E(q_{0})$
$r_{i+1}\in E(r')$ , var för någon $r'\in \Delta (r_{i},a_{i+1})$ $i=0,...,n-1$
$r_{n}\in F$ .

Ord. Det första villkoret säger att maskinen startar från ett tillstånd som är nåbart från tillståndet via ε-övergångar. Det andra villkoret säger att efter avläsning väljer maskinen övergången från till och utför sedan valfritt antal ε-övergångar enligt övergången från till . Det sista villkoret säger att maskinen accepterar om det sista inmatade tecknet får maskinen att övergå till ett av de accepterade tillstånden. Annars sägs automaten avvisa strängen. Uppsättningen strängar som den accepterar är det språk som automaten känner igen , och detta språk betecknas som .

q_{0}

a_{i}

\Delta

r_{i}

r'

\Delta

r'

r_{i+1}

w

M

M

L(M)

Exempel

Låt det finnas en NFA-ε med ett binärt alfabet som avgör om inmatningssträngen innehåller ett jämnt antal nollor eller ett jämnt antal ettor. Observera att 0 förekomster är ett jämnt tal. $M$

I formell notation, låt , där övergångsrelationen kan definieras av en sådan tillståndsövergångstabell : $M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta ,S_{0} ,\{S_{1},S_{3}\})$ $\Delta$

Ingångstat	0	ett	ε
S0 _	{}	{}	{ S 1 , S 3 }
S1 _	{ S2 } _	{ S 1 }	{}
S2 _	{ S 1 }	{ S2 } _	{}
S3 _	{ S 3 }	{ S4 } _	{}
S4 _	{ S4 } _	{ S 3 }	{}

$M$ kan ses som en förening av två DFA , en med stater och den andra med stater . Språket kan beskrivas som ett reguljärt språk som ges av det reguljära uttrycket (1*(01*01*)*) ∪ (0*(10*10*)*). Vi definierar med ε-övergångar, men vi kan definiera utan dem. $\{S_{1},S_{2}\}$ $\{S_{3},S_{4}\}$ $M$ $M$ $M$

Ekvivalens av NFAs

För att visa att NFA-ε är ekvivalent med NFA, notera först att NFA är ett specialfall av NFA-ε, det återstår att visa att det för alla NFA-ε finns en motsvarande NFA.

Låt det vara NFA-ε. NFA motsvarar , där för alla och . $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))$

Då är NFA-ε ekvivalent med NFA. Eftersom NFA är ekvivalent med DFA, är NFA-ε också ekvivalent med DFA.

Stängningsegenskaper

En NFA sägs vara stängd under en ( binär / unär ) operation. Om NFA känner igen språken som erhålls genom att tillämpa denna operation på de språk som erkänns av NFA. NFA är stängda med avseende på följande operationer.

Sammanfogning (se bild)
genomskärning
Sammankoppling
Tillägg
Kleene stängning

Eftersom NFA är ekvivalenta med ε-transition nondeterministic finite automata (NFA-ε), bevisas stängningarna ovan med användning av stängningsegenskaperna för NFA-ε. Det följer av stängningsegenskaperna ovan att NFA endast känner igen vanliga språk .

NFAs kan byggas från vilket reguljärt uttryck som helst med Thompson-algoritmen .

Egenskaper

Maskinen startar från ett visst initialtillstånd och läser en teckensträng som består av bokstäverna i dess alfabet . Automaten använder övergångsfunktionen Δ för att bestämma nästa tillstånd från det aktuella tillståndet och tecknet eller den tomma strängen som just lästs. Men nästa tillstånd för NFA beror inte bara på den aktuella inmatningssymbolen, utan också på ett godtyckligt antal efterföljande ingångshändelser. Medan dessa efterföljande händelser äger rum är det omöjligt att avgöra vilket tillstånd maskinen är i” [13] . Om automaten är i det slutliga tillståndet efter det senast lästa tecknet, sägs NFA acceptera strängen, annars sägs den avvisa strängen.

Uppsättningen av alla strängar som accepteras av NFA är det språk som NFA accepterar. Detta språk är ett vanligt språk .

För vilken NFA som helst kan man hitta en deterministisk finit automat (DFA) som accepterar samma språk. Därför är det möjligt att konvertera en befintlig NFA till en DFA för att implementera en (eventuellt) enklare maskin. En sådan transformation utförs med hjälp av delmängdskonstruktionen , vilket kan leda till en exponentiell ökning av antalet nödvändiga tillstånd. För ett formellt bevis på delmängdens konstruktion, se artikeln " Undermängdskonstruktion ".

Implementering

NFA kan modelleras på något av följande sätt:

Konvertera till motsvarande DFA. I vissa fall kan detta leda till en explosiv tillväxt av antalet stater [14] .
Upprätthålla uppsättningen av alla stater där NFA kan befinna sig efter att ha läst ordet. Vid bearbetning av en inmatningssymbol är det nödvändigt att kombinera resultaten av övergångsfunktionen som tillämpas på den aktuella uppsättningen av tillstånd för att få nästa uppsättning. Om ε-övergångar tillåts måste man även inkludera alla tillstånd som kan nås via sådana övergångar (ε-stängning). Varje steg kräver högst beräkningar, där s är antalet NFA-tillstånd. Automaten accepterar en sträng om och endast om, vid bearbetning av det sista inmatade tecknet, ett av de aktuella tillstånden är slutgiltigt. En sträng med längden n kan bearbetas i O (ns 2 ) tid [15] med O ( s ) minne. $s^{2}$

NCA Applications

NFA och DFA är likvärdiga i den meningen att om ett språk känns igen av en NFA av en automat, så känns det också igen av en DFA. Det omvända är också sant. Att fastställa en sådan likvärdighet är viktigt och användbart. Viktigt eftersom NFA kan användas för att minska komplexiteten i det matematiska arbete som behövs för att etablera viktiga egenskaper inom algoritmteorin . Till exempel är det mycket lättare att bevisa att vanliga språk är stängda med NFA än med DFA. Användbart eftersom att bygga en NFA för att erkänna att språket ibland är mycket viktigare än att bygga en DFA för det språket.

Se även

Deterministisk tillståndsmaskin
Tvåvägs icke-deterministisk ändlig maskin
Automatisk med magasinminne
Turing maskin

Anteckningar

↑ Martin, 2010 , sid. 108.
↑ Rabin och Scott, 1959 , sid. 114–125.
↑ En valsekvens kan leda till en "återvändsgränd" där ingen av övergångarna är giltiga för den aktuella inmatningssymbolen, och detta fall anses vara ett misslyckande (strängen avvisas).
↑ Hopcroft, Ullman, 1979 , sid. 19.
↑ Aho, Hopcroft & Ullman 1974 , sid. 319.
↑ Hopcroft, Ullman, 1979 , sid. 19-20.
↑ Sipser, 1997 , sid. 48.
↑ Hopcroft, Motwani, Ullman, 2001 , sid. 56.
↑ Aho, Hopcroft & Ullman 1974 , sid. 320.
↑ Sipser, 1997 , sid. 54.
↑ Hopcroft, Ullman, 1979 , sid. 21.
↑ Hopcroft, Motwani, Ullman, 2001 , sid. 59.
↑ Finite-State Machine FOLDOC Free Online Dictionary of Computing . Datum för åtkomst: 11 februari 2020. Arkiverad från originalet den 4 april 2015. (obestämd)
↑ Chris Calabro. NFA till DFA sprängs. 2005-02-27 . Hämtad 11 februari 2020. Arkiverad från originalet 7 februari 2013. (obestämd)
↑ Hopcroft, Motwani, Ullman, 2001 , sid. 153.

Litteratur

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Design och analys av datoralgoritmer . - Läsning/MA: Addison-Wesley, 1974. - ISBN 0-201-00029-6 .
- Aho A., Hopcroft J., Ulman J. Konstruktion och analys av beräkningsalgoritmer. - Moskva: Mir, 1979.
John E. Hopcroft, Jeffrey D. Ullman. Introduktion till automatteori, språk och beräkningar . - Läsning/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Introduktion till automatteori, språk och beräkningar . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion till automatteori, språk och beräkningar. - M . : "Williams" , 2002. - 528 sid. - ISBN 0-201-44124-1 .
Michael Sipser. Introduktion till teorin om beräkning . - Boston/MA: PWS Publishing Co., 1997. - ISBN 0-534-94728-X .
John Martin. Introduktion till språk och beräkningsteori. - McGraw Hill, 2010. - ISBN 978-0071289429 .
Rabin MO, Scott D. Finite Automata och deras beslutsproblem // IBM Journal of Research and Development. - 1959. - April ( vol. 3 , nummer 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. Lägga till spårmatchning med fria variabler till AspectJ // In Handlingar från den 20:e årliga ACM SIGPLAN-konferensen om objektorienterad programmering, system, språk och applikationer . — San Diego, CA, USA: OOPSLA '05. ACM, New York, NY, 2005. s. 345-364. Arkiverad 18 september 2009 på Wayback Machine

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm