Automatas de Pila

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 22

AUTÓMATA 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?

De igual manera que los lenguajes


regulares se pueden representar
mediante autómatas finitos
deterministas, los lenguajes
independientes del contexto tienen
su correspondencia en otro tipo de
dispositivo: el Autómata a Pila
(AP).
1
¿QUE ES UNA AUTÓMATA DE PILA?
Un autómata a pila es un dispositivo que tiene acceso a:

• Una secuencia de símbolos de entrada, que en general


se representa por una cinta que se desplaza frente a un
mecanismo de captación de dichos símbolos.

• El símbolo superior de una memoria en pila (LIFO).

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

Generalmente, el autómata a pila es no determinista en el sentido de


que se permite que haya varias acciones posibles en cada
momento.
3
AUTÓMATA DE PILA-GRÁFICAMENTE
(Cinta que almacena Símbolos de entrada)
(O palabra a ser analizada)
LECTURA
ESCRITURA
a a b b b Introducen y
Extraen Símbolos

CINTA PILA(LIFO-Last In, First Out; último en


entrar, primero en salir)

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:

• En el estado inicial (q0).


• Con sólo un símbolo en la pila (A0).
• Con la cabeza lectora en el primer símbolo de la entrada.

A partir de esta configuración realiza transiciones según la definición de la


función f.
12
NOTACIÓN GRÁFICA
Parecida a la de los diagramas de los autómatas finitos:

Para las transiciones se usa “ω/α/𝞫”

ω = Es la entrada (secuencia de caracteres) que se consume.


α = Es lo que se saca de la pila.
𝞫 = Es lo que se introduce en la pila.

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 Γ*

Cuando el autómata se encuentra en el estado q, lee el símbolo de entrada a y


tiene el símbolo A en la cima de la pila; el autómata pasará a algún estado qi
(recordar que es no determinista), eliminará el símbolo A de la pila e
introducirá en ella la palabra Zi , quedando la cabeza de Zi en la cima de la
pila.
14
INTERPRETACIÓN DE LA FUNCIÓN DE
TRANSICIÓN
b) f(q, λ, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)}
Cuando el autómata se encuentra en el estado q, y tiene el símbolo A en la cima
de la pila; el autómata pasará a algún estado qi (recordar que es no
determinista), eliminará el símbolo A de la pila e introducirá en ella la palabra
Zi , quedando la cabeza de Zi en la cima de la pila.

Se entiende que el resultado de la función f para las configuraciones (estado,


símbolo de entrada y símbolo de pila) no explícitamente especificadas es el
conjunto vacío. Estas representan configuraciones “muertas” del autómata.
15
Quizizz

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) = ∅

2. ∀q∈Q, ∀A∈Γ, ∀a∈ Σ∪{λ}:


f(q, a, A) contiene como máximo un elemento.

17
AUTÓMATAS A PILA DETERMINISTAS

A lo sumo, desde una configuración cualquiera existe como mucho un posible


movimiento.

A diferencia de los autómatas finitos, se entiende que un AP es no determinista,


a menos que se diga lo contrario.

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

También podría gustarte