PDF de programación - Tema 2: Autómatas finitos - Teoría de autómatas y lenguajes formales I

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 de 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)

© 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á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 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

filas: estados

• Representación tabular de la función δ
•
• columnas: entradas
• estado inicial: flecha
• estados finales: *

0
q2
q1

q2

->q0
*q1
q2

1
q0
q1

q1

© 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

,(ˆ
wq
δ

)

,(ˆ(
δδ

axq
),

)

=

• Ejemplo: Diseñar el AFD que 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

AL
(

(ˆ
w
{)
δ=

wq
,
0

)

pertenece

Fa

}

© 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

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
B

->A
*B

1
B
A

© Manuel Mucientes

Tema 2: Autómatas finitos

9

Autómatas finitos no deterministas
• AFN: capacidad de estar en varios estados simultáneamente
• Aceptan los lenguajes regulares, igual que los AFD
• Más compactos y fáciles de diseñar que los AFD
• Siempre es posible convertir un AFN a un AFD
• Ejemplo: AFN que acepta las cadenas terminadas en 01

© Manuel Mucientes

Tema 2: Autómatas finitos

10

Definición de los AFN

• A = (Q, Σ, δ, q0, F)

•

δ devuelve ahora un conjunto de estados, y no un sólo
estado

• Ejemplo: AFN que acepta las cadenas terminadas en 01

– A=({q0, q1, q2}, {0, 1}, δ, q0, {q2})

0

{q0, q1}

∅
∅

->q0
q1
q2

1
{q0}
{q2}
∅

© Manuel Mucientes

Tema 2: Autómatas finitos

11

Función de transición extendida

• Base:

}{),(ˆ
q
q
=∈δ

• Paso inductivo:

– w = xa,

–

–

=

,{),(ˆ
xq
pp
δ
1
k
(
δU
=

ap
i

rr
,{),
1

i

1
=

,

...,

2

kp

}

,(ˆ
wq
δ

rr
,{)
=
1

,

...,

2

mr

}

,

...,

2

r
m

}

• Ejemplo: describir el proceso de la entrada 00101 para el

autómata:

• Lenguaje de un AFN:

AL
(

(ˆ|{)
=
δ

w

wq
,
0

)

}
∅≠∩

F

© Manuel Mucientes

Tema 2: Autómatas finitos

12

Equivalencia entre AFD y AFN

• Todo lenguaje descrito por un AFN también puede ser

descrito por un AFD
– peor caso:

• AFN más pequeño: n estados
• AFD más pequeño: 2n estados

• Demostración de que un AFD puede hacer lo mismo

que un AFN: construcción de subconjuntos
– construcción de todos los subconjuntos del conjunto de estados

del AFN

© Manuel Mucientes

Tema 2: Autómatas finitos

13

Construcción de subconjuntos

• Dado el AFN N= (QN, Σ, δN, q0, FN), obtener el AFD D= (QD, Σ,

δD, {q0 }, FD) tal que L(D)=L(N)
– Alfabetos iguales
– Estado inicial: conjunto con el estado inicial de N
– QD: conjunto de subconjuntos de QN. Si QN tiene n estados, QD tendrá 2n.

Eliminación de estados no accesibles

– FD: conjunto de subconjuntos S de QN tales que
– Para cada y cada símbolo de entrada a:

NQS ⊆

∅≠∩ NFS

δ
D

aS
),(

δ
N

(

ap
),

U=

Senp

© Manuel Mucientes

Tema 2: Autómatas finitos

14

“Evaluación perezosa”

• Base: el conjunto de un elemento que contiene el estado inicial

de N es accesible

• Paso inductivo: hemos determinado que el conjunto S de

estados es accesible. Entonces, para cada símbolo de entrada
a, se calcula el conjunto de estados δD(S, a), que también
serán accesibles

• Ejemplo: aplicar el proceso al siguiente autómata

© Manuel Mucientes

Tema 2: Autómatas finitos

15

Equivalencia entre AFD y AFN

• Teorema: si D= (QD, Σ, δD, {q0 }, FD) es el AFD construido a

partir del AFN N= (QN, Σ, δN, q0, FN) mediante la
construcción de subconjuntos, entonces L(D)=L(N)

• Teorema: un lenguaje L es aceptado por algún AFD si y

sólo si L es aceptado por algún AFN

© Manuel Mucientes

Tema 2: Autómatas finitos

16

Problemas

•

Convertir el siguiente AFN en AFD

0

{p, q}
{r, s}
{p, r}
∅
∅

0
B
C
C
B

->p
q
r
*s
*t

->A
B
*C
*D

1
{p}
{t}
{t}
∅
∅

1
A
B
D
A

Solución:

A = {p}
B = {p, q}
C = {p, q, r, s}
D = {p, t}

© Manuel Mucientes

Tema 2: Autómatas finitos

17

Problemas

•

Convertir el siguiente AFN en AFD

Solución:

0

{p, q}
{r}
{s}
{s}

1
{p}
{r}
∅
{s}

0
B
D
E
F
F
F
E
E

1
A
C
A
C
G
G
H
H

->p
q
r
*s

->A
B
C
D
*E
*F
*G
*H

A = {p}
B = {p, q}
C = {p, r}
D = {p, q, r}
E = {p, q, s}
F = {p, q, r, s}
G = {p, r, s}
H = {p, s}

© Manuel Mucientes

Tema 2: Autómatas finitos

18

Una aplicación: búsqueda de texto

• Dado un conjunto de palabras, encontrar todos los

documentos que contienen una o más de esas
palabras.

• Motor de búsqueda: índices invertidos
• Características que hacen apropiado el uso de

autómatas en una aplicación:
– el depósito cambia rápidamente

• noticias del día
•

robot de compras

– los documentos no pueden ser catalogados: Amazon (páginas

generadas a partir de consultas)

© Manuel Mucientes

Tema 2: Autómatas finitos

19

AFN para búsqueda de texto

• Estado inicial con transición a sí mismo para cada símbolo de

entrada (conjetura)

• Para cada palabra clave a1a2...ak, hay k estados, q1, q2, ..., qk
• Transición del estado inicial a q1 con a1, de q1 a q2 con a2, etc.
El estado qk indicará que la palabra a1a2...ak ha sido aceptada

• Ejemplo: AFN que reconoce las palabras web y ebay

© Manuel Mucientes

Tema 2: Autómatas finitos

20

Ejemplo

Conversión del siguiente AFN en AFD

© Manuel Mucientes

Tema 2: Autómatas finitos

21

AFN con transiciones ε (AFN- ε)

• Transiciones para la cadena vacía, ε
• No expande la clase de lenguajes que aceptan los AF
• Proporciona “facilidades de programación”
• Ejemplo: AFN-ε que acepta números decimales

© Manuel Mucientes

Tema 2: Autómatas finitos

22

Notación

• A = (Q, Σ, δ, q0, F), pero ahora δ es una función de:

– un estado de Q
– un elemento de Σ U {ε}

• El símbolo ε no puede formar parte del alfabeto
• Ejemplo:

->q0

ε
{q1}
∅q1
∅q2
{q5}
q3
∅q4
*q5
∅

+, -
{q1}
∅
∅
∅
∅
∅

.
∅
{q2}
∅
∅
{q3}
∅

0, 1, ..., 9

∅

{q1, q4}
{q3}
{q3}
∅
∅

© Manuel Mucientes

Tema 2: Autómatas finitos

23

Clausuras respecto de ε

• Clausura del estado q respecto de ε, CLAUSε(q)

– Base: el estado q está en CLAUSε(q)
– Paso inductivo: si δ es la función de transición del AFN-ε, y el estado p

está en CLAUSε(q), entonces CLAUSε(q) contiene todos los estados de
δ(p, ε)

• Ejemplos: determinar las clausuras de los estados de los

autómatas de las siguientes figuras

© Manuel Mucientes

Tema 2: Autómatas finitos

24

Transiciones y lenguajes extendidos
• Definición recursiva de
CLAUS

– Base:
– Paso inductivo: sea w = xa, donde a es un elemento de Σ

),(ˆ
q
=∈δ

δˆ
q
)(

∈

}p , ... ,p ,{p
k

1

2

)

=

}r , ... ,r ,{r
m

1

2

• Sea

),(ˆ
=xqδ
k

(
δU
• Sea
i
1
=
,(ˆ
wq
)
δ

•

,

api
m

CLAUS

r
)(
j

∈

= U

1
=

j

• Lenguaje de un AFN-ε, E=(Q, Σ, δ, q0, F):

• Ejemplo: calcular para el autómata de la figura

EL
(

(ˆ|{)
w
=
δ
(ˆ
0qδ
)6.5,

wq
,
0

)

}
∅≠∩

F

© Manuel Mucientes

Tema 2: Autómatas finitos

25

Eliminación de transiciones ε

• Dado un AFN-ε E = (QE, Σ, δE, q0, FE), encontrar un AFD

D=(QD, Σ, δD, qD, FD) que acepte el mism