tema 2 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ñadeningú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 de estados, Q
– un conjunto finito de símbolos deentrada, Σ
– 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 del AFD: 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
– no se ha leído la secuencia 01, pero la entrada másreciente 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 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

© 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: *

->q0

*

q1
q2

© Manuel Mucientes

0

1

q2

q0

q1

q1

q2

q1

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 AFD que acepte el lenguaje L = {w | w
tiene un número par tanto de 0 como de 1}. Probar laentrada
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 conjunto de cadenas terminadas en 00
3. El conjunto de cadenas cuyo tercer símbolo desde el extremo derecho
seaun 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.

© Manuel Mucientes

0

1

->A A

B

*B

A

B

Tema 2: Autómatas finitos

9

Autómatas finitos no deterministas
•
•
•
•
•

AFN: capacidad de estar en varios estados simultáneamente...