Automatas de Pila
Automatas de Pila
Automatas de Pila
DETERMINISTA
Integrantes: Game Master: Maria Alexandra
Espinosa Carreño
● Danna Idalid Jimenez Forero
● Oscar Mauricio Ortega Borrero Materia: Teoría de la computación
● Fausto Orlando Francis Stephenson
● Santiago Andres Martinez Tarazona
¿QUE ES UNA AUTÓMATA DE PILA?
2
¿QUE ES UNA AUTÓMATA DE PILA?
Un autómata a pila se encuentra en cada momento en un estado
determinado y el estado siguiente depende de los tres elementos
siguientes:
• Estado actual
• Símbolo de entrada
• Símbolo superior de la pila
Unidad de
CABEZAL q0 control
q1
A
q2
A
Reglas, Producciones
Z0
4
FUNCIONES SOBRE LA PILA
Para el manejo de los
elementos almacenados en
la pila cuenta con dos
operaciones básicas: apilar
(push), que coloca un objeto
en la pila, y su operación
inversa, retirar (o desapilar,
pop), que retira el último
elemento apilado.
5
Quizizz
6
COSAS A TENER EN CUENTA EN LOS
AUTÓMATAS DE PILA
● La pila tendrá un alfabeto propio, que puede o no coincidir con el alfabeto
de la palabra de entrada. Esto se justifica porque puede ser necesario
introducir en la pila caracteres especiales.
● Se debe señalar que un AP no puede realizar ningún movimiento si la pila
está vacía.
● Un aspecto crucial de la pila es que solo podemos modificar su “tope”, que
es el extremo por donde entran o salen los caracteres. Los caracteres a la
mitad de la pila no son accesibles sin quitar antes los que están encima de
ellos.
7
CARACTERÍSTICAS DE UN AUTÓMATA
DE PILA
● Los autómatas de pila pueden aceptar lenguajes que no pueden
aceptar los autómatas finitos.
● Un autómata de pila cuenta con una cinta de entrada y un
mecanismo de control que puede encontrarse en uno de entre un
número finito de estados.
● A diferencia de los autómatas finitos, los autómatas de pila
cuentan con una memoria auxiliar llamada pila.
8
CARACTERÍSTICAS DE UN AUTÓMATA
DE PILA
● Los símbolos (llamados símbolos de pila) pueden ser insertados o
extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO).
● Las transiciones entre los estados que ejecutan los autómatas de
pila dependen de los símbolos de entrada y de los símbolos de la
pila.
● El autómata acepta una cadena x si la secuencia de transiciones,
comenzando en estado inicial y con pila vacía, conduce a un estado
final, después de leer toda la cadena x.
9
DEFINICIÓN FORMAL DE UN AUTÓMATA DE
PILA
AP = (Σ, Γ, Q, A0, q0, f, F)
Σ es el alfabeto de entrada.
Γ es el alfabeto de la pila.
Q es un conjunto finito de estados.
A0 ∈ Γ es el símbolo inicial de la pila.
q0 ∈ Q el esta inicial del autómata.
f es una aplicación denominada Función de transición de ternas
(estado, símbolo de entrada o λ símbolo de pila) en el conjunto de las
partes Q×Γ*
F ⊆ Q es el subconjunto de estados finales. 10
Quizizz
11
FUNCIÓN DE TRANSICIÓN DE UN
AUTÓMATA DE PILA
f : Q×{Σ∪{λ}}× Γ → 2Q×Γ* (subconjunto finito)
Un AP comienza su funcionamiento en la configuración inicial:
Ejemplo:
“a/λ/A” Índice que se consume de la entrada un carácter a, no se saca nada de la
pila y se mete b a la pila
13
INTERPRETACIÓN DE LA FUNCIÓN DE
TRANSICIÓN
(a, b,...) los elementos de Σ
(A, B, C..) los de Γ
(x, y, z,...) los de Σ* a) f(q, a, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)}
(X, Y, Z,...) los de Γ*
16
REPRESENTACIÓN GRÁFICA
17
AUTÓMATAS A PILA DETERMINISTAS
Decimos que un autómata a pila es determinista si se verifica lo
siguiente:
1. ∀ q∈Q, ∀ A∈Γ:
f(q, λ, A) ≠ ∅ ⇒ ∀ a∈Σ: f(q, a, A) = ∅
17
AUTÓMATAS A PILA DETERMINISTAS
18
AUTÓMATAS A PILA DETERMINISTAS
Ejemplo:
AP (por vaciado de pila) para L={anbmcp | n≥0, m≥1, p≥ n+m}
19
BIBLIOGRAFÍA
VIDEOS ONLINE:
● https://www.youtube.com/watch?v=Zv80KxbXzK8
● https://www.youtube.com/watch?v=YjEPHAJJAzg
● https://www.youtube.com/watch?v=APWCNaKOKIo
● https://www.youtube.com/watch?v=-I7o_Qip4wY
DOCUMENTOS ONLINE:
● http://www.ia.urjc.es/grupo/docencia/automatas_itis/apuntes/capitulo11.pdf