Automatas

Autómatas finitos deterministas (AFD)
• Determinista: para cada entrada, existe un único estado al que el autómata puede llegar partiendo del estado actual • Consta de:

Tabla de transiciones
Representación tabular de la función " • filas: estados • columnas: entradas • estado inicial: flecha • estados finales: *
0 ->q0 q2 q1 q2 1 q0 q1 q1

Tema 2: Autómatas finitos

– un conjunto finitode estados, Q – un conjunto finito de símbolos de entrada, ! – una función de transición (") que, dados un estado y una entrada, devuelve un estado. "(q, a) = p – un estado inicial (uno de los estados de Q), q0 – un conjunto de estados finales o de aceptación (subconjunto de Q), F

• A = (Q, !, ", q0, F)

*q1
q2
Teoría de autómatas y lenguajes formales I
© Manuel Mucientes (Revisión: JuanC. Acosta)

Tema 2: Autómatas finitos

4

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: Autómatas finitos

7

Bibliografía
• Hopcroft, J. E., Motwani, R., y Ullman, J. D. “Introducción a la Teoría de Autómatas, Lenguajes y Computación”. Addison Wesley. 2002.
– capítulos 2 y 4

Funcionamiento de un AFD
• Lenguaje del AFD: conjunto de las cadenas que acepta • Ejemplo: AFDque acepta todas las cadenas de ceros y unos que contienen la secuencia 01 en algún lugar de la cadena
• {w | w tiene la forma x01y, donde x e y son cadenas de símbolos 0 y 1} • {x01y | x e y son cadenas cualesquiera de 0 y 1}

Extensión a cadenas
• Función de transición: " • Función de transición extendida: "ˆ
– dado un estado q y una cadena w, devuelve un estado p

• Sudkamp, Thomas A.“Languages and machines : an introduction to the theory of computer science”. Addison-Wesley Publishing Company, 1998.
– capítulo 6

– se ha leído la secuencia 01: independientemente de las futuras entradas, el estado debe ser de aceptación – no se ha leído la secuencia 01, pero la entrada más reciente es 0: si se lee un 1, se pasa a estado de aceptación – no se ha leído la secuencia 01, y laentrada más reciente es un 1 o no existe: se aceptará la cadena cuando se lea 01 (esperar a la siguiente) – A = ({q0, q1, q2}, {0, 1}, ", q0, {q1})

• Definición por inducción de la función de transición extendida ˆ – Base: " ( q,$) # q
– Paso inductivo:

"ˆ ( q, w) # " ("ˆ ( q, x ), a )

• Ejemplo: Diseñar el AFD que acepte el lenguaje L = {w | w tiene un número par tanto de 0's como de 1's}.Probar la entrada 110101 • Lenguaje de un AFD: lenguaje regular

L( A) # {w "ˆ ( q0, w) pertenece a F }
© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: Autómatas finitos

2

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: Autómatas finitos

5

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: Autómatas finitos

8

Introducción
• Máquinas secuenciales
– Mealy– Moore

Diagrama de transiciones
• Es un grafo
– – – – un nodo por cada estado de Q un arco de q a p etiquetado con a para cada "(q, a) = p una flecha dirigida al estado inicial los estados finales están marcados por un doble círculo

Tarea para entrega
1. Construir los AFD que acepten los siguientes lenguajes sobre el alfabeto {0, 1}
1. El conjunto de cadenas con 011 como subcadena 2.El conjunto de cadenas terminadas en 00 3. El conjunto de cadenas cuyo tercer símbolo desde el extremo derecho sea un 1 4. El conjunto de cadenas que empiezan o terminan por 01

• • •

Autómatas de estados finitos: son máquinas secuenciales Reconocen los lenguajes regulares Clasificación
– Determinista (AFD): el autómata no puede estar en más de un estado simultáneamente – No determinista(AFN): puede estar en varios estados al mismo tiempo

•

No determinismo
– no añade ningún lenguaje a los ya definidos por los AFD (no es más expresivo) – aumento de la eficiencia en la descripción de una aplicación

2. Dado el siguiente AFD, describir de manera informal el lenguaje que acepta, y demostrarlo por inducción sobre la longitud de la cadena de entrada.
0 ->A A *B B 1 B A
9...