Automatas Finitos

Tema 2: Autómatas finitos

Teoría de autómatas y lenguajes formales I

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

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

© Manuel Mucientes

Tema 2: Autómatas finitos

2

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

• • •

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 – aumento de la eficiencia en la descripción de una aplicación

© Manuel Mucientes

Tema 2: Autómatas finitos

3

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:
– un conjunto finito deestados, 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)

© Manuel Mucientes

Tema 2: Autómatas finitos

4

Funcionamiento de un AFD
• Lenguaje delAFD: conjunto de las cadenas que acepta • Ejemplo: AFD que 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}

– se ha leído la secuencia 01: independientemente de las futuras entradas, el estado debe ser de aceptación – nose 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 la entrada más reciente es un 1 o no existe: se aceptará la cadena cuando se lea 01 – A = ({q0, q1, q2}, {0, 1}, δ, q0, {q1})

© Manuel Mucientes

Tema 2: Autómatas finitos

5

Diagrama de transiciones
• Es un grafo
– – – – un nodo por cadaestado 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

© Manuel Mucientes

Tema 2: Autómatas finitos

6

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*

q1 q2

© Manuel Mucientes

Tema 2: Autómatas finitos

7

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

• Definición por inducción de la función de transición extendida ˆ – Base: δ ( q,∈) = q
– Paso inductivo: w = xa

δˆ( q, w) = δ (δˆ( q, x ), a )

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

L( A) = {w δˆ( q 0, w) pertenece a F }
© Manuel Mucientes

Tema 2: Autómatas finitos

8

Problemas
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 conjuntode 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

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
© Manuel Mucientes

1 B A
9

B

Tema 2: Autómatas finitos...