CIRCUITOS
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...
Regístrate para leer el documento completo.