Autómatas Push Down

Autómatas
Push Down
Ing. Lucila Patricia Arellano
Mendoza

Autómata Push Down
Un autómata push down APD o autómata
de pila, es un autómata que reconoce
lenguajes de contexto libre (tipo 2).Un APD esta compuesto de una cuerda
de entrada, un control finito de estados y
una pila o stack.
Cuerda de entrada

┤
Pila o stack

Cabezas lectoras

Control finito

▼
Símbolo de pilavacía

de estados
Q

Fin de cadena

El paso de un estado a otro en un APD
depende de:
1.
2.
3.

El estado en el que nos encontremos
El elemento de la cuerda de entrada que
esta siendoapuntado
El elemento del tope de la pila

Un APD esta definido como una estructura algebraica de la
siguiente forma:
APD={Q,AE,AP,q0,z0,F,P}
Q=
AE=
AP=
q0=
z0=
F=
P=

donde:Conjunto de estados del autómata
Alfabeto de entrada del autómata
Alfabeto de pila
Estado inicial del autómata
Estado inicial de la pila
Conjunto de estados finales
Conjunto de reglas de transferenciaOperaciones en un APD
1.
Los estados
a) Pasar de un estado a otro dependiendo de la
cuerda de entrada y del alfabeto de la pila
b) Permanecer en el mismo estado
2.
La cuerda de entrada
a)Retener el símbolo actual
b) Pasar al siguiente elemento (avanzar)
3.
La pila o stack
a) Realizar un push
b) Realizar un pop
c) No hacer ninguno de los anteriores

Tabla de control
La tablade control se realiza por estado
del autómata.

Símbolos de la pila

qn

Símbolos del alfabeto

Función de
Transferencia

Configuración de un APD
Se define configuración de una autómatade pila a su
situación en un instante, que se puede expresar
formalmente mediante el terceto:
(q,w, α)
Donde:
q - estado del control finito
w - es la cadena de entrada que queda por ser leídaestando su primer elemento bajo la cabeza lectora
del APD
α - es el contenido de la pila en el instante considerado,
si α =▼ indica que la pila esta vacía

En un autómata push down se requiere...