Automata

La función de transición δ puede ser expresada mediante una tabla como la
siguiente, para este ejemplo:
q σ δ ( q , σ )
q 0 a q 1
q 0 b q 2
q 1 a q 1
q 1 b q 1
q 2 a q 0
q 2 b q 2
•La diferencia entre los diagramas de estado y los AFD en notación formal es
solamente de notación, siendo la información exactamente la misma, por lo que es
sencillo pasar de una representación ala otra.
• Tanto en los diagramas de estado como en la representación formal hay que tener
cuidado en respetar las condiciones para que tengamos un autómata valido; en
particular, el número detransiciones que salen de cada estado debe ser igual a la
cantidad de caracteres del alfabeto, puesto que δ es una función que está definida
para todas las entradas posibles.
• Reacuérdese queuna función no puede tener más de un resultado (en este caso, un
estado de llegada) para cada entrada en este caso, un estado de salida y un caracter
consumido).
• Para el ejemplo de la figura2.4, donde el alfabeto es {a, b}, de cada estado deben
salir exactamente dos transiciones, una con a y otra con b. • Otra condición es que debe haber exactamente un estado inicial, en cambio, lacantidad de estados finales puede ser cualquiera, inclusive cero, hasta un máximo de
|K | (la cantidad de estados).
• En la notación formal también hay que seguir las transiciones, que ahora no sonrepresentadas como flechas, sino como elementos del conjunto δ de transiciones.
• Tomando nuevamente el autómata de la figura 2.4 y la palabra de entrada bb, la
operación se inicia en el estadoinicial q0 ; luego, al recibir la primera b, usando la
transición ((q0 , b), q2 ) pasa a q2 , y luego, al recibir la segunda b de la palabra de
entrada, por medio de la transición ((q2 , b), q2 )pasa al estado q2
–de hecho
permanece en él.
• De una manera más general, si un AFD se encuentra en un estado q y recibe un
carácter σ pasa al estado q’ ssi δ ( q, σ ) = q’ , esto es, si (( q,...