1. Autmatas de Estados Finitos Ing. Edecio R. Freitez

2. AUTMATA FINITOS DETERMINISTICOAutmata Finito Deterministico .(AFD)Autmata: Es una maquina o sistema que puede aceptar unaentrada y posiblemente producir una salida, y que tendr algntipo de memoria interna que podr registrar cierta informacin delas entradas previas.Definicin de AFD: Un AFD, es una coleccin de cincoelementos(5-tupla) denotada por: M=(Q, , s, F, ) donde:- Q: Es una coleccin finita de estados.(Q= q ,q ,....,q )- : Es un alfabeto de entrada.- s: Representa el estado inicial (s Q, s=q )- F: Es una coleccin de estados finales o de aceptacin .- : Es una funcin de transicin de la forma: : QX ---------- Q donde 3. AUTMATA FINITOS DETERMINISTICO i , se tiene que: q , a =q , con a(a, es un smbolo), significa que seacual sea el estado actual y el carcter de la entrada, siemprehay un estado siguiente asociado a este par y el mismo esnico. Para toda cadena W y smbolo a de entrada se tiene que : q , Wa =W ,a . 4. AUTMATA FINITOS DETERMINISTICORepresentacin: Existen dos formas de representar un AFD. Diagrama de Transicin de Estado(DTE): Es una coleccinfinita de crculos los cuales se pueden rotular(anotar, apuntar) confines de referencia, conectados con flechas que reciben elnombre de arcos. Cada uno de estos arcos se etiqueta con unsimbo0lo o categora de smbolo (ej. Letras o dgitos) que podranestar presentes en la cadena que se analiza.- Uno de los crculos es designado con un apuntador, yrepresenta la posicin inicial.- Por lo menos unos de los crculos se representa como uncirculo doble, estos crculos dobles designan posiciones deldiagrama en las cuales se ha reconocido una cadena valida. 5. AUTMATA FINITOS DETERMINISTICO Tabla de Transicin(TT): Es un arreglo bidimensional cuyoselementos proporcionan el resumen del diagrama de transicin deestado. En las filas se colocan los estados de Q, en las columnaslos smbolos del alfabeto , y en la posicin (q , a) se coloca (q, a). A continuacin se presenta un ejemplo de un AFD: 6. AUTMATA FINITOS DETERMINISTICO Cadena Valida o Aceptada: Se dice que una cadena es aceptada por unDTE, si los smbolos que aparecen en la cadena (de izquierda a derecha),corresponden a una secuencia de arcos rotulados que conducen del estadoinicial a un circulo doble. Ejemplo: Sea el AFD dado por: M=(Q, , s, F, ) donde, Q= q0 , q1 ; 0, 1 ; s=q0 ;F= q1 ; : dada por:q0 ,0 =q0 ; q0 ,1 =q1 ; q1 ,0 =q1 ; q1 ,1 =q0- Obtenga la tabla de transicin y el diagrama de transicin de estadoasociado al AFD dado.- Verifique la validez de las cadenas siguientes para el AFD dado.W =01000; w =01001 7. AUTMATA FINITOS DETERMINISTICOSolucin:- Tabla de Transicin Asociada al AFD: (qi, ) 01 q0 q0 q1 q1 q0 q1 - Diagrama de Transicin de Estados: 8. AUTMATA FINITOS DETERMINISTICO Evaluando la cadena w =01000, se tiene que (q , 01000)= q ,0),1),0),0),0)=q ; La cadena no esAceptada(q , 010011)=q ,0),1),0),0),1)=q ; La cadena esAceptada. Definicin: Si M es un AFD, entonces el lenguaje aceptadopor M es:L(M)= W/ W es aceptada por M .Ejemplo: Sea el AFD, dado por: 9. AUTMATA FINITOS DETERMINISTICO El lenguaje aceptado por el AFD dado anteriormente es: L(M)= W/ W=(Cadenas de cero o ms yes (Y) que contienen un numero par de equis(X) ) . Nota: Es importante resaltar que L(M), esta formada por todas las cadenas aceptadas por M, y no que es un conjunto de cadenas que son todas aceptadas por M. 10. AUTMATA FINITO NO DETERMINISTICOSi se permite que desde un estado, se realicen cero, una o mstransiciones mediante el mismo smbolo de entrada, se dice queel autmata es no deterministico. El no determinismo consiste(intuitivamente) en agregar transiciones que antes estabanprohibidas: saltos con varios smbolos sobre la flecha, saltosvacos y saltos a ms de un estado con el mismo smbolo.Definicin: Un AFND, va a estar formado mediante unacoleccin de cinco elementos, denotados por: M=(Q, , s, F, )dondeQ: Conjunto finito de Estados: Alfabeto de Entradas: Representa el estado Inicial(s=q ).F Q: Coleccin o conjunto de Estados finitos o de aceptacin: Relacin sobre Q x x Q y se llama relacin de transicin 11. AUTMATA FINITO NO DETERMINISTICOObservacin: puesto que es una relacin para todo par (q,0)compuesto por el estado actual y el smbolo de la entrada. (q,0),es una coleccin de ceros o ms estados. es decir, (q,0) Q .Esto significa que, para todo estado q, se puede tener cero o masalternativas a elegir como estado siguiente, todas para el mismosmbolo de entrada.Representacin de un AFND: Al igual que los AFDS, los AFND,pueden ser representados por medio de la tabla de transiciny por medio del diagrama de transicin de estado. Acontinuacin se describen cada una de estas dos formas. 12. AUTMATA FINITO NO DETERMINISTICOTabla de transicin. En las filas estarn los estados q Q El estado inicial se preceder del smbolo Cada estado final se preceder del smbolo * En las columnas estarn los smbolos a{ } En la posicin (q,a) estarn los estados en (q,a)Diagrama de transicin de estado.- En los nodos estarn los estados- El estado inicial tendr un arco entrante no etiquetado- Los estados finales estarn rodeados de doble circulo- Habr un arco etiquetado con a ( ) entre el nodo qi si qj (qi,a) 13. AUTMATA FINITO NO DETERMINISTICOEjemplo: Sea el AFND M dado por:Q= q 0, q1 , q2 , q3 , q4 ;a, b ; s= q0 ; F= q2 ,q3,q4 ; : dada por:abq0{q1,q4{q3} }q1 {q1} {q2}q2q3q4 {q4} 14. AUTMATA FINITO NO DETERMINISTICOEl Diagrama de Transicin Asociado a M, semuestra a continuacin: 15. AUTMATA FINITO NO DETERMINISTICOObservacin: Como se aprecia en la tabla de relacin de transicin las celdasson conjuntos. Las celdas con vaco( ), indican que no existe ningunatransicin desde el estado actual mediante la entrada correspondiente. Quepara un estado actual, smbolo de entrada exista mas de un posible estadosiguiente, significa que se puede elegir entre las distintas posibilidades. Elejemplo dado no existe nada que determine la eleccin hacia un nico estado,por tal razn se dice que el comportamiento del autmata es no deterministico.Definicin: Si M es un AFND, entonces el lenguaje aceptado por M es:L(M)= W / W es aceptada por M . Nota: En el caso particular del ejemplo anterior cabe destacar que ellenguaje aceptado por dicho autmata es: L(M)= 16. EQUIVALENCIA ENTRE AFD Y AFND 17. EQUIVALENCIA ENTRE AFD Y AFNDEjemplo: Sea el AFND M dado por: Q={q0, q1,q2}; ={a,b};S={q0} y F={q0} y : dada por:ab q0 {q1} q1 {q0,q2} q2 {q0} Obtenga un AFD M = (Q , , s F , ) que sea equivalente.Defina todas las componentes. 18. EQUIVALENCIA ENTRE AFD Y AFNDSolucin: El DTE asociado a M, viene dado por : 19. EQUIVALENCIA ENTRE AFD Y AFND 20. EQUIVALENCIA ENTRE AFD Y AFND A continuacin se presenta el diagrama de transicin de estadoresultante: 21. AFND CON -TRANSICIONES - transiciones: Son aquellas transiciones que al realizarse noconsumen ningn smbolo de entrada,, es decir; son transicionesde un estado a otro que no dependen de ninguna entrada. Ejemplo: Sea el AFND, dado por: 22. AFND CON -TRANSICIONES Comentario: El autmata puede cambiar su estado de q0 sinconsumir nada en la entrada. q1 , es el nico estado deaceptacin del AFND presentado, si W es cualquier cadenade cero o ms aes, el autmata cicla sobre q0 hasta queconsuma las aes, una vez que la cadena se vaca se desplaza aq1 y la acepta. Ejemplo: Sea El AFND dado por: 23. AFND CON -TRANSICIONES Comentario: El AFND dado puede moverse de q a q sinconsumir nada en la entrada. En los ejemplos citados, la decisinde elegir una -transicin, se realiza de la misma forma que lade cualquier otra transicin con eleccin mltiple que exista enun AFND. Por lo tanto las -transiciones son consistentes con elmatiz no deterministico de los AFND. Construccin de la Tabla de Transicin: Si un AFND tiene -transiciones, la relacin asocia pares de Q X ( U( )) X Q consubconjuntos de Q .( Es decir es una relacin sobre Q X( U( )) X Q, se puede aadir una nueva columna en la tabla depara colocar los pares de la forma (q, ). Ejemplo: Para el DTE del ejemplo anterior se tiene que la tablaseria: 24. AFND CON -TRANSICIONESab q0 {q1}q1 {q2}q2 {q0} {q0} Nota: Cuando hay -transiciones en n AFND es conveniente suponer que cada estadotiene una -transicin que cicla en ese estado. En el caso del ejemplo anterior la tablaquedara de la siguiente forma a b q0 {q1} {q0} q1 {q2}{q1} q2 {q0} {q0,q2} 25. AFND CON -TRANSICIONESNota: Para calcular el conjunto de estados siguientes en unAFND, que contiene -transiciones se deben tener en cuenta las -transiciones anteriores y posteriores a la transicin etiquetadacon. Ejemplo: Sea el AFND dado por. 26. AFND CON -TRANSICIONES Conjunto de estados siguientes a: (q , a)= q , q (q , b)= q , q , q Nota: Para l calculo del conjunto de estados siguientes en unAFND con -transiciones se deben tener en consideracin lasdefiniciones dadas a continuacin. Definicin: Para todo estado q Q, se define la -cerradura de qcomo sigue.-c(q)= p / p es accesible desde q sin consumir nada en laentrada , ampliando la definicin dada para todo el conjuntode estados se tiene que: 27. AFND CON -TRANSICIONES Ejemplo: Sea el AFND, dado por: Obtener : -c(q3 ); -c(q1 ); -c(q4 )Solucin:-c(q3 )= q3 ; -c(q1 )= q1 , q2 ;-c(q )= q0 ,q2 , q4 28. AFND CON -TRANSICIONES Definicin: Para todo q Q y , se tiene que d(q, )= p / hay una transicin de q a p etiquetada con ,ampliando esta definicin a todo el conjunto Q, se tiene que. Ejemplo: Para el AFND del ejemplo dado anteriormenteobtener, d(q0,a); d(q1, b); d q3,q4 , b .Solucin:d(q0,a)= q3 ; d(q0, b)= ;d q3,q4 , b = d q3 , b)U q4 , b = q4 U q0 = q0,q4 29. AFND CON -TRANSICIONES Definicin: A partir de un AFND que tiene transiciones sepuede tener un AFND sin -transiciones que acepte el mismolenguaje. Se define M =(Q, , s, F , ) donde:F = FU q / - c(q)F (q, )= - c(q, )= - c (d( - c(q), )) Ejemplo: Sea el AFND con - transiciones dado por: 30. AFND CON -TRANSICIONES 31. AFND CON -TRANSICIONESSolucin: (q0,a)= - c(d( - c(q0),a))= q1,q3,q4,q5 se tiene que- c(q0)= q0,q1 ;d( q0,q1 ,a)= q3,q4- c q3,q4 )= q1,q3 ,q4,q5 (q0,b)= q2 ; (q1,a)= q4,q5 ; (q1,b)= q2 ; (q2,a)= ; (q2,b)= ; (q3,a)= q2,q5 ; (q3,b)= q2,q4,q5 ; (q4,a)= ;(q4,b)= ; (q5,a)= ;(q5,b)= ; 32. AFND CON -TRANSICIONES A continuacin se muestra el DTE asociado al AFND sin -transiciones. 33. CONCEPTOS RELATIVOS A AFD Y AFND Extensin a palabras: dado que la solo transita cuando recibeun smbolo de entrada, se puede generalizar para cuando recibeuna palabra formada por mas de un smbolo o por palabra vaca. Aceptacin de palabras: x * es aceptada o reconocida por unAFD si f (qo, x) F. Es decir, si se parte del estado inicial yrecibe la palabra de entrada x, se transita a un estado que perteneceal conjunto de estados finales o de aceptacin F. 34. CONCEPTOS RELATIVOS A AFD Y AFND Lenguaje reconocido por un AFD: es el conjunto de palabras aceptadas por unAFD. As se comprueba que existe entre autmatas y lenguajes de forma quecada autmata reconoce un lenguaje determinado (regular en el caso de la Af),generando como salida una aceptacin si la palabra de entrada pertenece allenguaje y una no-aceptacin si la palabra de entrada no pertenece al lenguaje.Tambin existe la relacin inversa que permite asegurar que, para cada lenguajeregular, hay un AF que reconoce palabras de ese lenguaje y no reconoceninguna palabra que no pertenezca al lenguaje. Accesibilidad entre estados: p Q es accesible desde q Q, pAp, si existeuna palabra x * tal que f (q, x)=p. A efectos de simplificar los autmatas,todos aquellos estados no accesibles desde el inicial, se pueden borrar, ya queno afectaran al comportamiento del autmata al no poder llegar nunca a ellos. 35. CONCEPTOS RELATIVOS A AFD Y AFNDAutmatas Conexos: Un AFD es conexo si para cada estadoqi Q, qi es accesible desde qj . Equivalencia entre estados: Dos estados p, q Q sonequivalentes pEq, six , (p,x) F (q,x) F Nota: Si las transiciones de p con la entrada x llegan a un estadofinal las transiciones de q con x tambin tienen que llegar, y silas transiciones de p con x no llegan a un estado final lastransiciones de q con x tampoco deben llegar. 36. GRACIAS POR SU ATENCION