Unidad 5: Autómatas con PILA Flashcards
Un autómata con pila es un AF al que se le incorpora una memoria
Qué tipo de memoria tiene un autómata con pila?
LIFO
Qué lenguaje reconocen los autómatas con pila?
Lenguajes tipo 2: independientes de contexto
Cuál es la definición formal de los AP?
AP = (ΣE, Γ, Q, q0, #, A, f )
donde:
ΣE : Alfabeto de símbolos de entrada
Γ : Alfabeto de símbolos de la pila
Q : Conjunto finito y no vacío, de estados posibles
q0 : Estado inicial de operación, (pertenece a Q)
A : Conjunto de estados de aceptación, (pertenece a Q)
#: Símbolo de referencia de pila (pertenece a ΣE y Γ)
f : Función de transición
Cuál es la función de transición del AP?
f: Q x (ΣE U {λ}) x Γ → Q x Γ*
A partir de f se define:
a) el comportamiento se define según el estado actual, el símbolo de entrada y el símbolo de tope de pila.
b) A partir del comportamiento se define el próximo estado y la acción sobre la pila
Cuáles son las condiciones de no determinismo de un AP?
Un AP es no determinista si:
a) en un cierto tiempo, el APND opera sin leer la cadena de entrada (transición λ)
b) múltiples opciones de próximo estado y carga de pila
c) ambas
Concepto de configuración instantánea.
Siendo la configuración instantánea la condicion en la que se encuentra el AP en un intrevalo de tiempo dado.
Kt = ( q , β , δ)
donde:
q es el estado en el que se encuentra el AP
β es la subcadena de entrada pendiente de ser leída
δ es el contenido de la pila
Cuál es la configuración inicial y final?
La configuración inicial del AP es
K0 = ( q0 , α , # )
y la configuración final es
Kn = ( q , λ , δ )
Cuál es el movimiento del AP?
( p , aβ, δb ) ├─ ( q , β, δbb )
solo puede existir si existe la transición f(p, a, b) = (q, bb): el movimiento del estado p a q, leyendo el símbolo a, extrayendo de la pila el símbolo b y almacenando bb
Cuál es el movimiento desde la configuración inicial a la configuración final?
( q0 , α, # ) ├─* ( q , λ, δ)
Cuales son las formas de aceptación de lenguajes por los APs?
a) Aceptación por vaciado de pila:
L = {α / (q0, α, #) ├─* (q, λ, #) con q0,q∈Q, α∈pΣE*, #∈Γ}
b) Aceptación por estado de aceptación
L = {α / (q0, α, #) ├─* (q, λ, δ) con q0∈Q, q∈A, α∈ΣE*, δ∈Γ+, #∈Γ}
c) Aceptación por ambos
L = {α / (q0, α, #) ├─* (q, λ, #) con q0, q∈Q, q∈A, α∈ΣE*, #∈Γ}
Los APD y APND son equivalentes?
NO, como los APND tienen más poder de cómputo gracias al no determinismo, los lenguajes aceptados por los APND son más generales que los aceptados por los APD
Si bien puede existir un APD equivalente que acepte algunas cadenas, pero es menos general
Top Down Parser
Qué enfoque de derivación tiene el Analisador sintáctico descendente?
Tiene un enfoque descendente: a partir del axioma “S” identifica las producciones que sucesivamente se aplican para derivar por izquierda la cadena.
Genera el árbol de derivación desde la raíz hacia las hojas.
Bottom Up Parsers
Qué enfoque de derivación tiene el Analisador sintáctico ascendente?
Tiene un enfoque ascendente: se parte de la cadena de entrada y se identifican las reducciones a realizar para construitr una derivación por derecha. Genera el arbol desde las hojas hacia la raíz.
Dado que los analisadores son APND,
Qué problema implica la validación de cadenas?
El espacio de estados requerido para analizar cadenas queda representado por un árbol con elevado factor de ramificación, lo que impacta a la eficiencia del proceso.
Qué es el preanálisis?
Una técnica que implica conocer anticipadamente los próximos k símbolos a ser leídos, para determinar su próximo movimiento (prediciendo cuál de las posibles producciones conduce a la aceptación)
El preanálisis hace que un APND funcione en forma determinista, frente a alternativas no deterministas
Cuáles son los algoritmos de análisis sintáctico de los AS Predicitivos?
LL(k): Left to right read and leftmost derivation (ASD)
LR(k): Left to right read and rightmost derivation (ASA)
donde k es la cantidad de símbolos a preanalizar
Variaciones de LR(k)
LR(0)
- No utiliza preanálisis, se usa cuando las gramáticas no generan transiciones alternativas.
- Más facil de implementar
- Menos poder de reconocimientos
Variaciones de LR(k)
SLR(1)
- Simple LR
- utiliza un solo símbolo de preanálisis
Variaciones de LR(k)
LR(1)
- LR clásico que utiliza un solo símbolo de preanálisis
- Su AP conduce estructuras de datos muy grandes
Variaciones de LR(k)
LALR(1)
- Look Ahead LR
- Combina la potencia de LR(1) con la eficiencia del SLR(1)
