Autòmat finit no deterministaUn 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 un AFND pot donar-se qualsevol d'aquests dos casos:
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ó formalFormalment, si bé un autòmat finit determinista es defineix com una 5 - tupla ( Q , Σ, q 0 , δ, A ) on:[1]
en un AFND la funció de transició es defineix com: Per al cas dels AFND-ε, se sol expressar la funció de transició de la forma: 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. FuncionamentLa 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:
AFND-εPropietatsPer tot , s'escriu si i només si a es pot arribar des , anant al llarg de zero o més fletxes . En altres paraules, si i només si existeix on tal que
Per a qualsevol , el conjunt d'estats que es pot arribar a partir de p s'anomena epsilon-closure o ε-closure de p i s'escriu com
Per a qualsevol subconjunt , definir el ε-closure de P com
Les transicions epsilon són transitive, ja que pot demostrar que per a tot i , si i , llavors . De la mateixa manera, si i llavors 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 1 x 2 ... x n , on x i ∈ (Σ ∪{ε}), i una seqüència d'estats p 0 , p 1 , ..., p n , on p i ∈ Q , compleixen les següents condicions:
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:
ExempleL'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 0 , F ) on:
El diagrama d'estats per M és: M pot ser vist com la unió de dos AFDs: un amb els estats{ S 1 , S 2 }i l'altre amb els estats{ S 3 , S 4 }. El llenguatge de M pot ser descrit pel llenguatge regular donat per l'expressió regular: Vegeu tambéReferències
Bibliografia
Information related to Autòmat finit no determinista |