CIRCUITOS

Autómatas de Pila

Autómatas y Matemáticas Discretas

Tema 3: Gramáticas y lenguajes libres de contexto
3.1.- Introducción
3.2.- Gramáticas Libres de Contexto
3.3.- Árboles de Derivación
3.4.- Simplificación de Gramáticas Libres de Contexto
3.5.- Formas Normales de Chomsky y Greibach
3.6.- Autómatas de Pila
3.7.- Propiedades de los Lenguajes Libres de Contexto

Conocimientos previos-

Relaciones
Descripciones Instantáneas en AF
Manejo de gramáticas
Diseño de alguna gramática sencilla
FNC y FNG
Determinismo - No Determinismo en AF

-1

-

Autómatas de Pila

3.6 Autómatas de Pila (Push - Down)
1. Introducción
Un Autómata de Pila es aquella máquina que
reconoce lenguajes generados por gramáticas libres de
contexto (GLC).

0 0 0 1 1 1

Cinta de entradaQ

Pila
(memoria)
C
C
C

control de estados

Funcionamiento de un AP:

1.- Dependiente de la entrada.
f: estado x pila x cinta

estado x pila*

2.- Independiente de la entrada.
f: estado x pila x {λ}

estado x pila*

(*) De la pila se lee un solo símbolo pero puede escribir una cadena
-2

-

Autómatas de Pila

Aceptación de las cadenas
• Por vaciado de la pila
•Por estados finales

¿Un Autómata para reconocer L={0n1n | n ≥ 0}?
0
0-0

1

0

0

3-0

2-0

1-0

1

2-1

1

1
10-1
1

0 0 0 1 1 1

Cinta de entrada

Q

Pila
(memoria)
C
C
C

control de estados

-3

-

Autómatas de Pila

2. Definición Formal de AP
Definición.
Un AP es una séptupla (Σ, Γ, Q, Z0, q0, f, F) donde:
Σ es el alfabeto de entrada
Γ es elalfabeto de la pila
Q es el conjunto finito de estados
Z es el símbolo inicial de la pila
q0 es el estado inicial
f es una aplicación

f : Q × Σ ∪ {λ} × Γ→ P(Q × Γ*)

F es un subconjunto de Q que contiene los estados finales.

0 0 0 1 1 1

Cinta de entrada

Q

Pila
(memoria)
C
C
C

control de estados

-4

-

Autómatas de Pila

Descripción Instantánea(configuración).
(q, w, α)

· q representa al estado actual del autómata
· w es la cadena de entrada que falta por analizar, w ∈Σ*
si w = λ, toda la cadena de entrada ha sido leída.
· α es el contenido de la pila en el instante actual
si α = λ la pila está vacía, α ∈ Γ*

Movimiento.
Transición entre dos descripciones instantáneas
(q, aw, Zα) ├─ (q’, w, γα)

donde la función f para esta entrada tomael valor:
(q’, γ) ∈ f(q, a, Z)

NOTA:├─ representa una relación binaria ... ¿├─* ?

-5

-

Autómatas de Pila

• Configuración inicial:

(q0, w, Z) , w ∈Σ*
• Configuración final:

- AP por estados finales:
(p, λ, X)

con p ∈ F y X ∈ Γ*

- AP por vaciado de pila:
(p, λ, λ),

con p ∈ Q

Definición. Lenguaje aceptado por un AP.
• Lenguaje aceptado por estados finales por elAP

definido como AP = (Σ, Γ, Q, Z, q0, f, F):

{w ∈ Σ* | (q0, W, Z) ├─* (p, λ, X), con p ∈ F y X ∈ Γ*}
• Lenguaje aceptado por vaciado de pila por el AP

definido como AP = (Σ, Γ, Q, Z, q0, f, ∅) al conjunto:
{w ∈ Σ* | (q0, W, Z) ├─* (p, λ, λ), con p ∈ Q}

-6

-

Autómatas de Pila

EJEMPLO: AP que reconozca el LLC L={0n1n | n ≥1}
1) Alfabeto de entrada : Σ = {0, 1}
2) Alfabetode la pila Γ
Necesitamos registrar:
i) Llegada de un 0 ⇒ Metemos una C en la pila
ii) Llegada de un 1 ⇒ Quito una C de la pila
iii) El estado inicial de la pila ⇒ Z
Γ = {C, Z}
3) Conjunto de estados Q
Estado p: leyendo ceros (‘apilando’)
Estado q: comprobando unos (‘desapilando’)
Q = {p, q}
4) Empezaremos a funcionar en el estado p: q0 = p
5) El AP va a funcionar por vaciado de pila: F= ∅
6) El símbolo inicial de la pila: Z
7) Y por último la función se definirá como (*)
f(p, 0, Z) = {(p, CZ)}
f(p, 0, C) = {(p, CC)}
f(p, 1, C) = {(q, λ)}
f(q, 1, C) = {(q, λ)}
f(q, λ, Z) = {(q, λ)}
(*) con f definimos aquellos movimientos que hacen que las
cadenas del lenguaje sean aceptadas, no nos preocupamos por las
cadenas que ‘producirían error’.

-7

-

Autómatas de...