Automatas de Pila

SIS 762 Autmatas

1

Autmatas de Pila.

Introduccin.-

Un autmata de pila es un tipo de mquina, que recibe una cadena constituida por smbolos de

un alfabeto y determina si esa cadena pertenece al lenguaje que el autmata reconoce.

El autmata de pila cuenta con una cinta de entrada y un mecanismo de control, que puede

encontrarse en uno de entre un nmero finito de estados.

Donde a uno de estos estados se le designa como estado inicial, adems algunos estados se

llaman de aceptacin o estados finales. A diferencia de los autmatas finitos, los autmatas de

pila cuentan con una memoria auxiliar llamada pila. Los smbolos (llamados smbolos de pila)

pueden ser insertados o extrados de la pila.

Los autmatas de pila permiten reconocer los lenguajes independientes del contexto

correspondientes a las gramticas de tipo 2 dentro de la jerarqua de Chomsky. Cabe resaltar

que los lenguajes libres de contexto tienen una gran importancia en la definicin de los

lenguajes de programacin, interpretacin del lenguaje natural, construccin de compiladores

etc.

Transiciones de un autmata de pila. Estas transiciones hacen posible el cambio de estado del

autmata, cada vez que se recibe un carcter de la cinta de entrada es posible realizar un

cambio de estado y si tras leer el ultimo carcter de la cadena se permanece en un estado de

aceptacin, el autmata o mecanismo de control indica que la cadena es aceptada para ello es

necesario realizar los siguientes pasos:

Leer un smbolo de entrada

Extraer un smbolo de la pila

Insertar un smbolo en la pila

Pasar a un nuevo estado

Los smbolos (llamados smbolos de pila) pueden ser insertados o extrados de la pila, de

acuerdo con el manejo last-in-first-out (LIFO).

Las transiciones entre los estados que ejecutan los autmatas de pila dependen de los smbolos

de entrada y de los smbolos de la pila. El autmata acepta una cadena x si la secuencia de

transiciones, comenzando en estado inicial y con pila vaca, conduce a un estado final, despus

de leer toda la cadena x.

SIS 762 Autmatas

2

De manera formal un autmata de pila no determinstico esta dado de la siguiente definicin.

Se dice que un autmata de pila no determinstico M es una maquina formada por siete

elementos.

M = (Q,,,,q0,z,F)

Donde:

Q: Conjunto finito de estados internos (q0, q1, q2, q3, q4, q5,.. qn) estados.

: Smbolos de entrada denominados alfabetos de entrada.

: Conjunto finito de smbolos llamados alfabeto de pila.

: Funcin de transicin. : Q x ( U { } ) x Subconjunto finito de Q x *

q0: El estado inicial

Z : Smbolo inicial que contiene la pila antes de proceder a cualquier reconocimiento.

F: Conjunto de estados finales.

Cinta de entrada (contiene la cadena a ser leda)

Cabeza lectora (se nueve a la dercha)

PILA: permite recordar

Lo Ledo en la cinta

Mecanismo de Control