Automata de pila

4 Autómatas de Pila

4.1 AUTÓMATAS DE PILA (AP).
En el capítulo 2 hemos visto que los autómatas finitos son objetos equivalentes a
las gramáticas regulares, es decir que un lenguaje regular se corresponde, bien con
una gramática regular, bien con un autómata finito, aunque no de manera biunívoca,
según no nos hemos cansado de repetir. Vimos también que los lenguajes regulares
tienen suslímites, debido fundamentalmente a su incapacidad para contar. En este
capítulo nuestro punto de mira este puesto en las gramáticas independientes del
contexto y los lenguajes que generan, queremos definir un objeto genérico del tipo
autómata que valga para reflejar al menos este nivel de gramáticas.

4.1.1

DEFINICIÓN DE AUTÓMATA DE PILA.

Un autómata de pila es una séptuplaM=(Q,Σ,∆,q0,δ,F) donde:
Q= conjunto finito de estados
Σ= alfabeto de entrada
∆= alfabeto de pila
q0∈Q estado inicial

© Inmaculada Luengo

4. Autómatas de Pila

4.1 Autómatas de Pila (AP)

F⊆Q, F≠∅, conjunto de estados finales
δ es la función de transición, definida de la siguiente forma
Q × (Σ ∪ {λ}) × (∆ ∪ {λ}) ⎯δ P(Q × ∆ * )
⎯→
es decir la forma genérica de la imagen de una terna será
δ (q , a ,Z ) = {(r1 , ω1 ),L , (rk , ωk ); ri ∈ Q , ωi ∈ ∆ *}
Según esta definición un AP es en genral no determinista.
Una transición es una orden que permite, en el caso de que el autómata se
encontrara en estado q, en la cinta de entrada estuviera leyendo el símbolo a y el
símbolo de la cima de la pila fuera Z, transitar a cualquiera de los estados ri y,
extrayendo el símbolo Z de la pila,sustituirlo por la correspondiente palabra ωi.
Para visualizar un autómata de pila podemos imaginar los estados y la cinta de
entrada como en los autómatas finitos, pero ahora está la pila que podemos imaginar
como una cinta interna (que siempre representamos como una columna) donde se
van insertando o extrayendo los símbolos de pila según lo vayan mandando las
transiciones.
La pila hace el papelde una memoria rudimentaria: sobre ella se escriben
palabras y se van extrayendo símbolo a símbolo. Debe quedar claro el modo en que
entendemos que se insertan las palabras en la pila: Si ω = a1….ak es una palabra de
longitud k y queremos insertarla en la pila de un AP, entendemos que el símbolo que
queda en la cima de la pila es a1. Volveremos sobre ello más adelante.
Lo que no debemos ahoraes tratar de visualizar una transición no determinista
porque cada posibilidad lleva aparejado un estado diferente de la pila y se complica
mucho la notación si en cada instante representamos todas las posibles situaciones
actuales de la pila.
Antes de terminar este apartado estudiamos las transiciones definidas sobre ternas
"especiales",
62
© Inmaculada Luengo

4. Autómatas de Pila4.1 Autómatas de Pila (AP)

i) δ(q,λ,Z)= {(r1,ω1),….,(rk,ωk) : ri ∈Q, ωi ∈∆*}
se lee λ en la cinta de entrada, es decir: se transita sin avanzar en la cinta de
entrada.
ii) δ(q,a,λ)= {(r1,ω1),….,(rk,ωk) : ri ∈Q, ωi ∈∆*}
se extrae λ de la pila, es decir: se transita sin extraer nada de la pila, pero si
se inserta.
iii) δ(q,λ,λ)= {(r1,ω1),….,(rk,ωk) : ri ∈Q, ωi ∈∆*}
se transita sin avanzaren la cinta de entrada y sin extraer de la pila.

4.1.2

REPRESENTACIÓN GRÁFICA DE UN AP

Es similar a la de un autómata finito:
Dibujamos un círculo por cada estado no final y un doble círculo por cada
estado final.
Marcamos el estado inicial con una flecha de entrada, sin etiquetar.
Por cada (r,ω) ∈ δ(q,a,Z) dibujamos una flecha de q a r etiquetada a,Z;ω
El gráfico de un AP lo describecompletamente.

Ejemplo:
Sea M8 = (Q,Σ,∆,q0,δ,F,) con Q = {p,q,r,s}, Σ = {0,1}, ∆ = {#,a}, p estado inicial,
F={s}, y función de transición δ definida de la manera siguiente
δ(p,λ,λ)={(q,#)}
δ(q,0,λ)={(q,a)}
δ(q,1,a)={(r,λ)}
δ(r,1,a)={(r,λ)}
δ(r,λ,#)={(s,λ)}
La imagen de todas las demás ternas del conjunto de partida es ∅.
La representación gráfica de este AP será
63
©...