Automatas Push Down

Automatas Push Down

AUTÓMATAS DE PILA O PUSH -DOWN (PDA).

Un autómata de pila o Push-Down es un autómata que cuenta con un mecanismo que permita almacenamiento ilimitado y opera como una pila.

El autómata de pila (se abrevia PDA de sus siglas en inglés Push-Down Autómata) tiene una cinta de entrada, un control finito y una pila. La pila es una cadena de símbolos de algún alfabeto. El símbolo que se encuentra más a la izquierda se considera como que está en la “cima”. El dispositivo será no determinístico y tendrá un número finito de alternativas de movimiento en cada situación ver figura 3.1.

Autómata de pila.

Los movimientos serán de dos tipos. En el primer tipo de movimiento se utiliza un símbolo de entrada. Dependiendo del símbolo de entrada, del símbolo de la cima y el estado de control finito, es posible un número de alternativas.

Cada alternativa consiste en un estado posterior para el control finito y una cadena (posiblemente vacía) de símbolos, para sustituir al símbolo que se encuentra en la cima de la pila. Después de seleccionar una alternativa, la cabeza de entrada avanza un símbolo como se ilustra en la figura 3.2.

Para ver el gráfico seleccione la opción “Descargar” del menú superior

Avance de un símbolo de entrada (q1, c, B), a un estado posterior

y sustitución de la cima de la pila (q2, B).

El segundo tipo de movimiento conocido como movimiento e es parecido al primero, excepto que el símbolo de entrada no se utiliza y la cabeza de la entrada no avanza después del movimiento. Este tipo de movimiento permite al PDA manipular la pila sin leer símbolos de entrada como se muestra en la figura 3.3.

Para ver el gráfico seleccione la opción “Descargar” del menú superior

Manipulación de la pila sin leer símbolo de entrada.

Existen dos modos de aceptar un lenguaje por un autómata de apilamiento. El primero consiste en definir el lenguaje aceptado como el conjunto de todas las entradas para las cuales una sucesión de movimientos ocasiona que el autómata de pila vacíe su pila.

La segunda manera es designando algunos estados como estados finales y definimos el lenguaje aceptado como el conjunto de todas las entradas para las cuales alguna selección de movimiento ocasiona que el autómata de pila accese un estado final.

Un autómata de pila M es un sistema (Q, S , G , d , q0, Z0, F), en donde:

Q es un conjunto finito de estados.

S es el alfabeto llamado alfabeto de entrada.

G es el alfabeto, conocido como alfabeto de pila.

q0 Î Q, es el estado inicial.

Z0 Î G , es el símbolo llamado símbolo inicial.

F Í Q es el conjunto de estados finales.

d es una transformación de Q x (S È a {e }) x G en los subconjuntos finitos Q x G *.

Sea M=(Q, S , G , d , q0, Z0, F) un autómata de pila. El lenguaje aceptado por M se denota por L(M) y es el conjunto L(M) = {wÎ S *½ ( q0, w, Z0) * (p, e , u ) para pÎ F y uÎ G *}.

Nota: * se usa para denotar los movimientos con un número arbitrario de pasos, donde * indica “cero o más pasos”.

Obsérvese que la aceptación requiere que M se mueva a un estado final cuando la cadena w se agote. M puede terminar o no con la pila vacía. (Sin embargo, obsérvese que cuando la pila se vacía el PDA debe parar, ya que todas las transiciones requieren un símbolo de pila).

El siguiente ejemplo representa un autómata de pila que acepta a wcwR mediante un agotamiento de pila M=(Q, S , G , d , q0, Z0, F). Donde:

Q = {q1, q2} q0 = q1

S = {0, 1, C} Z0 = R

G = {R, B, G} F = Æ

y d está definida por:

d (q1, 0, R) = (q1, BR)

d (q1, 0, B) = (q1, BB)

d (q1, 0, G) = (q1, BG)

d (q1, c, R) = (q2, R)

d (q1, c, B) = (q2, B)

d (q1, c, G) = (q2, G)

d (q2, e , R) = (q2, e )

d (q1, 1, R) = (q1, GR)

d (q1, 1, B) = {(q1, GB

d (q1, 1, G) = (q1, GG)

d (q2, 1, G) = (q2, e )

Analizando la cadena 01C10 usando el PDA anterior se obtiene lo siguiente:

(q1, 01C10, R) por la regla 1 ® (q1, 1C10, BR) por la regla 10 ® (q1, C10, GBR) por la regla 6 ® (q2, 10, GBR) por la regla 12 ® (q2, 0, BR) por la regla 7 ® (q2, e , R) por la regla 8 ® (q2, e , e ) y se agota la pila.

Consideremos el siguiente ejemplo de autómata de pila definido por:

Q = {q1, q2, q3, q4}

S = {a, b}

G = {A,B}

Z0 = A

F = {q4}

q0=q1

y d dado por la siguiente tabla:

Ya que d depende del estado actual, el símbolo de entrada actual y el símbolo actual de la cima de la pila, la tabla tiene filas que corresponden a los estados y columnas que corresponden a los pares de símbolos de entrada y de la pila.

Obsérvese que no hay transiciones para todas las ternas posibles de estado, símbolo de entrada y símbolo de pila. Por lo tanto, si el PDA pasa a un estado para el cual no se especifica un estado siguiente y una acción de la pila para los símbolos actuales de la pila y la entrada, el PDA no puede volver a realizar ningún movimiento. En particular, cuando el autómata está en el estado q4, que es el estado de aceptación, no hay ninguna transición sea cual sea el símbolo de la cima y de la entrada.

Si el PDA se mueve al estado q2, entonces obsérvese que cada vez que a aparece en la entrada se apila una B en la pila. El PDA permanece en el estado q2 hasta que se encuentra la primera b y entonces se mueve al estado q3, ninguna b puede preceder a una a. Finalmente, en el estado q3 sólo se consideran las b’s y, cuando se encuentra cualquier b, se desapila B de la pila. (Sólo pueden desapilarse las B’s que fueron apiladas, debido a encontrarse una a en la entrada).

Las únicas cadenas que acepta el PDA pertenecen al lenguaje an bn È ā, puesto que son las únicas cadenas de entrada que, una vez que han sido consumidas, causan que el PDA termine en el estado final q4.

por:instituto tecnologioco de villahermosa


Mis sitios nuevos:
Emprendedores
Politica de Privacidad