Autòmat finit no determinista

Un autòmat finit no determinista (abreujat AFND ) és un autòmat finit que, a diferència dels autòmats finits deterministes (AFD), té almenys un estat q ∈ Q , tal que per a un símbol a ∈ Σ de l'alfabet, hi ha més d'una transició δ ( q , a ) possible.

En aquest exemple, δ ( q ₀ , b ) = q ₀ i δ ( q ₀ , b ) = q ₁ . Per tant, es tracta d'un autòmat finit no determinista, que reconeix l'expressió regular (a | b) * b ⁺.

En un AFND pot donar-se qualsevol d'aquests dos casos:

• Que hi hagi transicions del tipus δ ( q , a ) = q ₁ i δ ( q , a ) = q ₂ , sent q ₁ ≠ q ₂ ;
• Que hi hagi transicions del tipus δ ( q , ε), sent q un estat no-final, o bé un estat final però amb transicions cap a altres estats.

Quan es compleix el segon cas, es diu que l'autòmat és un autòmat finit no determinista amb transicions buides o transicions ε (abreujat AFND-ε ). Aquestes transicions permeten l'autòmat canviar d'estat sense processar cap símbol d'entrada. Considerem una modificació al model de l'autòmat finit per permetre cap, una o més transicions d'un estat sobre el mateix símbol d'entrada.

Definició formal

Formalment, si bé un autòmat finit determinista es defineix com una 5 - tupla ( Q , Σ, q ₀ , δ, A ) on:

• $Q\,$ és un conjunt d'estats;
• $\Sigma \,$ és un alfabet;
• $Q_{0}\in Q$ és l'estat inicial;
• $\Delta \colon Q\times \Sigma \to Q$ és una funció de transició;
• $F\subseteq S$ és un conjunt d'estats finals o d'acceptació.

en un AFND la funció de transició es defineix com:

$\Delta :Q\times \Sigma \to {\mathcal {P}}(Q)$

Per al cas dels AFND-ε, se sol expressar la funció de transició de la forma:

$\Delta :Q\times \{\Sigma \cup \epsilon \}\to {\mathcal {P}}(Q)$

on P (Q) és el conjunt potència de Q . Això significa que els autòmats finits deterministes són un cas particular dels no deterministes, ja que Q pertany al conjunt P (Q) .

La interpretació que se sol fer en el còmput d'un AFND és que l'autòmat pot passar per diversos estats al mateix temps, generant-se una ramificació de les configuracions existents en un moment donat. Així mateix, en un autòmat finit no determinista podem acceptar l'existència de més d'un node inicial.

Funcionament

La màquina comença en l'estat inicial especificat i llegeix una cadena de caràcters pertanyents a l'alfabet. L'autòmat utilitza la funció de transició d'estats T per determinar l'estat següent, utilitzant l'estat actual i el símbol que acaba de llegir o la cadena buida. No obstant això, "l'estat següent d'un AFND no només depèn de l'esdeveniment d'entrada actual, sinó que també en un nombre arbitrari dels esdeveniments d'entrada posterior. Fins que es produeixen aquests esdeveniments posteriors no és possible determinar en quin estat es troba la màquina ". Quan l'autòmat ha acabat de llegir, i es troba en un estat d'acceptació, es diu que el AFND accepta la cadena, en cas contrari es diu que la cadena de caràcters és rebutjada. Tant per a un AFND com per a un autòmat finit determinista (AFD) es pot acceptar el mateix llenguatge. Per tant, és possible convertir un AFND existent en un AFD per al desenvolupament d'una màquina potser més simple. Això es pot dur a terme utilitzant la construcció del conjunt potència, que pot conduir a un augment exponencial en el nombre d'estats necessaris.

Implementació

Hi ha moltes formes d'implementar una ANFD:

• Convertir l'equivalent AFE: en alguns casos això pot causar una explosió exponencial en la grandària de l'autòmat, i així un espai auxiliar proporcional al nombre d'estats en el ANFD (com l'emmagatzematge del valor de l'estat requereix en la majoria d'un bit per cada estat en el ANFD).

• Mantenir un conjunt de dades de tots els estats en què la màquina podria estar en l'actualitat. En consumir l'últim caràcter d'entrada, si un d'aquests estats és un estat final, la màquina accepta la cadena. En el pitjor dels casos, això pot requerir espai addicional proporcional al nombre d'estats en el ANFD, si l'estructura del conjunt fa servir un bit per estat del ANFD, llavors aquesta solució és exactament equivalent a l'anterior.

• Crear múltiples còpies. Per cada n forma de la decisió, el ANFD crea fins n-1 còpies de la màquina. Cada un d'ells entrés en un estat independent. Si, al moment de consumir l'últim símbol de l'entrada, almenys una còpia del ANFD està en un estat d'acceptació, el ANFD ho acceptarà. (Això també requereix un emmagatzematge lineal pel que fa al nombre d'estats del ANFD, ja que pot haver-hi una màquina per cada estat del ANFD).

AFND-ε

Propietats

Per tot $p,q\in Q,$, s'escriu $p{\stackrel {\epsilon }{\rightarrow }}q$ si i només si a $q$ es pot arribar des $p$, anant al llarg de zero o més fletxes $\epsilon$. En altres paraules, $p{\stackrel {\epsilon }{\rightarrow }}q$ si i només si existeix $Q_{1},Q_{2},\cdots Q_{k}\in Q$ on $k\geq 0$ tal que

$Q_{1}\in T(p,\epsilon ),Q_{2}\in T(Q_{1},\epsilon ),\cdots Q_{k}\in T(Q_{k-1},\epsilon ),q\in T(Q_{k},\epsilon )$.

Per a qualsevol $p\in Q$, el conjunt d'estats que es pot arribar a partir de p s'anomena epsilon-closure o ε-closure de p i s'escriu com

$\,I(\{p\})=\{q\in Q:p{\stackrel {\epsilon }{\rightarrow }}q\}$.

Per a qualsevol subconjunt $P\subset Q$, definir el ε-closure de P com

$E(P)=\bigcup \limits _{p\in P}E(\{p\})$.

Les transicions epsilon són transitive, ja que pot demostrar que per a tot $Q_{0},Q_{1},Q_{2}\in Q$ i $P\subset Q$, si $Q_{1}\in I(\{Q_{0}\})$ i $Q_{2}\in I(\{Q_{1}\})$, llavors $Q_{2}\in I(\{Q_{0}\})$.

De la mateixa manera, si $Q_{1}\in E(P)$ i $Q_{2}\in I(\{Q_{1}\})$ llavors $Q_{2}\in E(P)$ Sigui x una cadena de l'alfabet Σ ∪{ε}. Un AFND-ε M accepta la cadena x si existeix tant una representació de x de la forma x ₁ x ₂ ... x _n , on x _i ∈ (Σ ∪{ε}), i una seqüència d'estats

p ₀ , p ₁ , ..., p _n , on p _i ∈ Q , compleixen les següents condicions:

1. p ₀ $\in$ E ({ q ₀ })
2. p _i $\in$ E ( T ( p _i-1 , x _i )) per i = 1, ..., n
3. p _n $\in$ F .

Aplicació

El AFND i el AFD són equivalents en això, ja que si un llenguatge és reconegut pel AFND, també serà reconegut per un AFD, i viceversa. L'establiment d'aquesta equivalència és útil perquè de vegades la construcció d'un AFND per reconèixer un llenguatge determinat és més fàcil que construir un AFD per a aquest llenguatge. També és important perquè el AFND es pot utilitzar per reduir la complexitat del treball matemàtic necessari per establir moltes propietats importants en la teoria de la computació. Per exemple, és molt més fàcil demostrar les següents propietats utilitzant un AFND que un AFD:

• La unió de dos llenguatges regulars és regular.
• La concatenació de dos llenguatges regulars és regular.
• La Clausura de Kleene en un Llenguatge regular és regular.

Exemple

L'exemple següent mostra un AFND M , amb un alfabet binari que determina si l'entrada conté un nombre parell de 0s o un nombre parell de 1s. Llavors M = ( Q , Σ, T , s ₀ , F ) on:

• Σ ={0, 1},
• Q ={ s ₀ , s ₁ , s ₂ , s ₃ , s ₄ },
• E ({ es ₀ }) ={s ₀ , s ₁ , s ₃ }
• F ={ s ₁ , s ₃ }, i
• La funció de transició T pot ser definida per aquesta taula de transició d'estats:

	0	1	Ε
S 0	{}	{}	{ S 1 , S 3 }
S 1	{ S 2 }	{ S 1 }	{}
S 2	{ S 1 }	{ S 2 }	{}
S 3	{ S 3 }	{ S 4 }	{}
S 4	{ S 4 }	{ S 3 }	{}

El diagrama d'estats per M és:

M pot ser vist com la unió de dos AFDs: un amb els estats{ S ₁ , S ₂ }i l'altre amb els estats{ S ₃ , S ₄ }.

El llenguatge de M pot ser descrit pel llenguatge regular donat per l'expressió regular:

$(1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})$

Vegeu també

• Autòmat finit
• Autòmat finit determinista
• Construcció de subconjunts

Bibliografia

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Autòmat finit no determinista

• M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development , 3 : 2 (1959) pp.115-125.
• Michael Sips, Introduction to the Theory of Computation . PWS, Boston. 1997.
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation , Addison-Wesley Publishing, Reading Massachusetts, 1979.