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

Tema 5:

Autómatas a pila

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 6 y 7

• Sudkamp, Thomas A. “Languages and machines : an

introduction to the theory of computer science”.
Addison-Wesley Publishing Company, 1998.
– capítulos 8 y 5

© Manuel Mucientes

Tema 5: Autómatas a pila

2

Introducción a los autómatas a pila
• Un autómata a pila (AP) es un AFN con transiciones ε y

con una pila en la que se puede almacenar una cadena de
“símbolos de pila”

• El AP puede recordar una cantidad infinita de información

– LIFO

• Los AP reconocen todos los LIC y sólo estos

– existen lenguajes que no son LIC

•

{0n1n2n | }1≥n

© Manuel Mucientes

Tema 5: Autómatas a pila

3

Introducción a los AP (II)

• Se consume de la entrada un símbolo, o bien ε
• Se pasa a un nuevo estado
• Se reemplaza el símbolo en lo alto de la pila por una

cadena (podría ser ε)

© Manuel Mucientes

Tema 5: Autómatas a pila

4

Introducción a los AP (III)

• Ejemplo: diseñar el AP para el lenguaje Lwwr = {wwR | w está en

(0+1)*}
– se comienza en el estado q0

• suponemos que la cadena w aún no ha finalizado
• se almacena una copia de los símbolos de entrada leídos en la pila

– en cualquier momento se puede suponer que w ha finalizado y se ha

comenzado a leer wR

• el final de w estará en la cima de la pila
• se transita al estado q1
• AP no determinista:

– podemos suponer que hemos visto el final de w
– también podemos continuar en q0 almacenando las entradas en la pila

– en el estado q1 se compara el símbolo de entrada con el símbolo en la

cima de la pila

• son iguales: se elimina el símbolo de la pila
• son distintos: no habíamos llegado al final de w. Esa rama muere

– si se vacía la pila, hemos leído wwR y se acepta la entrada

© Manuel Mucientes

Tema 5: Autómatas a pila

5

Definición formal de los AP

• P = (Q, Σ, Γ, δ, q0, Z0, F)

– Q: conjunto finito de estados
– Σ: conjunto finito de símbolos de entrada
– Γ: alfabeto de pila finito
– δ: función de transición, δ(q, a, X) = (p, γ)
– q0: estado inicial
– Z0: símbolo inicial de la pila
– F: conjunto de estados de aceptación

© Manuel Mucientes

Tema 5: Autómatas a pila

6

Definición formal de los AP (II)

• Ejemplo: diseñar un AP que acepte el lenguaje Lwwr

– P = ({q0, q1, q2}, {0, 1}, {0, 1, Z0}, δ, q0, Z0, {q2}), donde δ se define:
ΓΣQ
0
q0
Z0
1
q0
Z0
00
q0
10
q0
01
q0
11
q0
q0
Z0
ε
q0
0ε
1ε
q0
00
q1
11
q1
q1
Z0
ε

Movimiento
(q0, 0Z0)
(q0, 1Z0)
(q0, 00)
(q0, 01)
(q0, 10)
(q0, 11)
(q1, Z0)
(q1, 0)
(q1, 1)
(q1, ε)
(q1, ε)
(q2, Z0)

© Manuel Mucientes

Tema 5: Autómatas a pila

7

Descripción instantánea de un AP
• Descripción instantánea: (q, w, γ)

– q es el estado
– w es la entrada que falta por leer
– γ es el contenido de la pila (la cima de la pila se muestra a la izquierda

de γ, y el fondo a la derecha)

• Sea δ(q, a, X) = (p, α). Para todas las cadenas w de Σ* y β de

Γ*:
– (q, aw, Xβ) ├ (p, w, αβ)
– cero o más movimientos del AP: ├*

• Notación

– alfabeto de entrada: a, b, ...
– estados: p, q, ...
– cadenas de símbolos de entrada: ..., w, x, y, z
– símbolos de pila: ..., X, Y, Z
– cadenas de símbolos de pila: α, β, γ, ...

© Manuel Mucientes

Tema 5: Autómatas a pila

8

Descripción instantánea de un AP (II)

• Ejemplo: acción del AP para la entrada 1111

© Manuel Mucientes

Tema 5: Autómatas a pila

9

Descripción instantánea de un AP (III)
• Teorema:

– si P = (Q, Σ, Γ, δ, q0, Z0, F) es un AP y
– (q, x, α) ├* (p, y, β),
– entonces para cualquier cadena w en Σ* y γ en Γ* es también cierto que

(q, xw, αγ) ├* (p, yw, βγ)

• Teorema:

– si P = (Q, Σ, Γ, δ, q0, Z0, F) es un AP y
– (q, xw, α) ├* (p, yw, β),
– entonces es también cierto que (q, x, α) ├* (p, y, β)

© Manuel Mucientes

Tema 5: Autómatas a pila

10

Problemas

1. Dado el AP P = ({q, p}, {0, 1}, {Z0 , X}, δ, q, Z0, {p}), donde δ se

define en la siguiente tabla, mostrar las configuraciones
alcanzables a partir de la inicial (q, w, Z0), para w igual a 01,
0011 y 010

ΓΣQ
0
q
Z0
X0
q
X1
q
q
Xε
p
Xε
X1
p
1
Z0
p

Movimiento

Soluciones:

(q, XZ0)
(q, XX)
(q, X)
(p, ε)
(p, ε)
(p, XX)
(p, ε)

• (q, 01, Z0) ├* (p, ε, Z0)
├* (p, ε, ε)

•(q, 0011, Z0) ├* (p, ε, XZ0)
├* (p, ε, XXZ0)

•(q, 010, Z0) ├* (p, ε, XZ0)

© Manuel Mucientes

Tema 5: Autómatas a pila

11

Lenguajes aceptados por un AP

• Dos tipos de aceptación

– por estado final
– por vaciado de pila

• Ambos métodos son equivalentes
• Aceptación por estado final

– sea P = (Q, Σ, Γ, δ, q0, Z0, F) un AP
– L(P), el lenguaje aceptado por P por estado final es
– {w | (q0, w, Z0) ├* (q, ε, α)}
– para algún estado q de F y cualquier cadena de pila α

© Manuel Mucientes

Tema 5: Autómatas a pila

12

Lenguajes aceptados por un AP (II)

• Ejemplo: el AP de la figura acepta cadenas x por estado

final si y sólo si x tiene la forma wwR

© Manuel Mucientes

Tema 5: Autómatas a pila

13

Aceptación por pila vacía

• Para todo AP P = (Q, Σ, Γ, δ, q0, Z0) se define el lenguaje que

acepta como:
– N(P) = {w | (q0, w, Z0) ├* (q, ε, ε)} para cualquier estado q

• Ejemplo: modificar el AP de la figura para que reconozca

también por vaciado de pila
– se cambia δ(q1, ε, Z0) = {(q2, Z0)} por δ(q1, ε, Z0) = {(q2, ε)}

© Manuel Mucientes

Tema 5: Autómatas a pila

14

De pila vacía a estado final

• Teorema: si L = N(PN) para algún AP PN = (Q, Σ, Γ, δN, q0,

Z0), existe un AP PF tal que L = L(PF)

• Prueba: PF = (Q

U

{p0, pF}, Σ, Γ

U

{X0}, δF, p0, X0, {pF}),

δF(p0, ε, X0) = {(q0, Z0X0)}

donde δF se define:
1.
2. para todo estado q de Q, entrada a de Σ o a = ε, y símbolos de
pila Y de Γ, δF(q, a, Y) contiene todos los pares de δN(q, a, Y)
3. además, δF(q, ε, X0) contiene (pF, ε) para todo estado q de Q

© Manuel Mucientes

Tema 5: Autómatas a pila

15

De pila vacía a estado final (II)
• Ejemplo: diseñar un AP que procese secuencias “if else”,

detectando cuando se introducen igual número de else que if
– PN = ({q, s}, {i, e}, {Z, A}, δN, q, A)

– PF = ({p, q, r, s}, {i, e}, {Z, A, X0}, δF, p, X0, {r})

ε, A/ε

s

Inicio

ε, X0/AX0

p

ε, A/ε

ε, X0 /ε

r

s

© Manuel Mucientes

Tema 5: Autómatas a pila

16

De estado final a pila vacía

• Teorema: sea L el lenguaje L(PF) de algún autómata a pila

PF = (Q, Σ, Γ, δF, q0, Z0, F). Entonces existe un AP PN tal que
L = N(PN)

• Prueba:PN = (Q

U

{p0, p}, Σ, Λ = Γ

U

{X0}, δN, p0, X0), donde

δN se define:
1.
2. para todo estado q de Q, entrada a de Σ o a = ε, y símbolos de pila Y

δN(p0, ε, X0) = {(q0, Z0X0)}

en Γ, δN(q, a, Y) contiene todos los pares de δF(q, a, Y)

3. para todo estado de aceptación q en F, y símbolos de pila Y en Λ,

δN(q, ε, Y) contiene (p, ε)

4. para todos los símbolos de la pila Y en Λ, δN(p, ε, Y)={(p, ε)}

Λ

Λ

Λ

© Manuel Mucientes

Tema 5: Autómatas a pila

17

Problemas

1. Diseñar un AP que acepte el lenguaje {0n1n |

1≥n

}

2. Dado el AP P = ({q0, q1, q2, q3, f}, {a, b}, {Z0, A, B}, δ, q0, Z0,

{f}), donde δ se define en la siguiente tabla
1. mostrar la traza de ejecución que muestre que la cadena bab está

en L

2. mostrar la traza de ejecución que muestre que la cadena abb está

en L

δ(q0, a, Z0) = (q1, AAZ0)
δ(q1, a, A) = (q1, AAA)
δ(q2, a, B) = (q3, ε)
δ(q3, ε, B) = (q2, ε)

δ(q0, b, Z0) = (q2, BZ0)
δ(q1, b, A) = (q1, ε)
δ(q2, b, B) = (q2, BB)
δ(q3, ε, Z0) = (q1, AZ0)

δ(q0, ε, Z0) = (f, ε)
δ(q1, ε, Z0) = (q0, Z0)
δ(q2, ε, Z0) = (q0, Z0)

© Manuel Mucientes

Tema 5: Autómatas a pila

18

Equivalencia entre AP y GIC

• El objetivo es demostrar que los tres siguientes lenguajes

son todos de la misma clase
1.
2.
3.

lenguajes independientes del contexto
lenguajes aceptados por estado final por algún AP
lenguajes aceptados por vaciado de pila por algún AP

– (2) y (3) ya se ha demostrado
– demostraremos el paso de (1) a (3), aunque no de (3) a

(1)

© Manuel Mucientes

Tema 5: Autómatas a pila

19

De gramáticas a AP

• Sea la GIC G = (V, T, Q, S). El AP que acepta L(G) por pila

vacía será:
– P = ({q}, T, V T, δ, q, S)
–

U
δ se define por:
1. para cada variable A, δ(q, ε, A) = {(q, β) | A
2. para cada símbolo terminal a, δ(q, a, a) = (q, ε)

β es una producción de P}

• Ejemplo: obtener el AP que reconozca por vaciado la

siguiente gramática: I
E+E | (E)

a | b | Ia | Ib | I0 | I1, E I | E*E |

© Manuel Mucientes

Tema 5: Autómatas a pila

20

Autómatas a pila deterministas
• Los APD aceptan un conjunto de lenguajes a medio camino

entre los lenguajes regulares y las GIC
– los analizadores sintácticos se comportan generalmente como APD

• Un AP P = (Q, Σ, Γ, δ, q0, Z0, F) es determinista si:

– δ(q, a, X) tiene como máximo un elemento para cualquier q en Q, a en Σ

o a= ε, y X en Γ

– si δ(q, a, X) no está vacío para algún a en Σ, δ(q, ε, X) debe estar vacío
• Ejemplo: sea Lwcwr = {wcwR | w está en (0 + 1)* }. El APD que

acepta dicho lenguaje es:

© Manuel Mucientes

Tema 5: Autómatas a pila

21

Problemas

1. Determinar si el siguiente AP es o no determinista: P = ({q, p},
{0, 1}, {Z0 , X}, δ, q0, Z0, {p}), donde δ se define en la siguiente
tabla

ΣQ
Γ
0
q
Z0
X0
q
X1
q
q
Xε
p
Xε
X1
p
1
Z0
p

Movimiento

(q, XZ0)
(q, XX)
(q, X)
(p, ε)
(p, ε)
(p, XX)
(p, ε)

© Manuel Mucientes

Tema 5: Autómatas a pila

22

Formas normales para GIC

• Las gramáticas en formas normales pueden generar todos

los LIC
– Forma Normal de Chomsky
– Forma Normal de Greibach

• Las gramáticas en formas normales reducen la

complejidad para la obtención de las derivaciones

• Para obtener una gramática en forma normal es necesario
realizar una serie de transformaciones que no modifican el
lenguaje generado:
– eliminación de producciones ε
– eliminación de producciones unitarias (reglas de encadenamiento)
– eliminación de símbolos inútiles

© Manuel Mucientes

Tema 5: Autómatas a pila

23

Eliminación de producciones ε

• Una variable es anulable si A ⇒* ε

•