AUTOMATA DE PILA

Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadenaconstituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky.

Formalmente, un autómata con pila puede ser descrito como una séptupla ${\displaystyle M=(S,\Sigma ,\Gamma ,\delta ,s,Z,F)}$ donde:

• ${\displaystyle S}$ es un conjunto finito de estados;
• ${\displaystyle \Sigma }$ y ${\displaystyle \Gamma }$ son alfabetos (símbolos de entrada y de la pila respectivamente);
• ${\displaystyle \delta :S\times (\Sigma \cup \{\epsilon \})\times \Gamma \rightarrow {\mathcal {P}}(S\times \Gamma ^{*})}$
• ${\displaystyle s\in S}$ es el estado inicial;
• ${\displaystyle Z\ \in \Gamma }$ es el símbolo inicial de la pila;
• ${\displaystyle F\subseteq S}$ es un conjunto de estados de aceptación o finales;

La interpretación de ${\displaystyle \delta (q,a,b)=\{(q_{1},\gamma _{1}),(q_{2},\gamma _{2}),\ldots ,(q_{n},\gamma _{n})\}}$, con ${\displaystyle q,q_{i}\in S,a\in (\Sigma \cup \{\epsilon \}),b\in \Gamma }$, y ${\displaystyle \gamma _{i}\in \Gamma ^{*}}$ es la siguiente:

Cuando el estado del autómata es ${\displaystyle q}$, el símbolo que la cabeza lectora está inspeccionando en ese momento es ${\displaystyle a}$, y en la cima de la pila nos encontramos el símbolo ${\displaystyle b}$, se realizan las siguientes acciones:

• Si ${\displaystyle a\in \Sigma }$, es decir no es la cadena vacía, la cabeza lectora avanza una posición para inspeccionar el siguiente símbolo.
• Se elimina el símbolo ${\displaystyle b}$ de la pila del autómata.
• Se selecciona un par ${\displaystyle (q_{i},\gamma _{i})}$ de entre los existentes en la definición de ${\displaystyle \delta (q,a,b)}$, la función de transición del autómata.
• Se apila la cadena ${\displaystyle \gamma _{i}=c_{1}c_{2}\ldots c_{k}}$, con ${\displaystyle c_{i}\in \Gamma }$ en la pila del autómata, quedando el símbolo ${\displaystyle c_{k}}$ en la cima de la pila.
• Se cambia el control del autómata al estado ${\displaystyle q_{i}}$.

AUTÓMATA DE PILA DETERMINISTICO

P = (Q, Σ, Г,Δ, q0, T,Z) donde:

• Q es un conjunto finito de estados.
• Σ es el alfabeto de entrada.
• Г es el alfabeto de la pila.
• q0 є Q es el estado inicial.
• Z є Г símbolo inicial de la pila.
• T es subconjunto de Q (conjunto de estados finales).
• Δ es la función de transición tal que:

         Δ: Q × (Σ U { ε }) × Г → (Q × Г *)

AUTÓMATA CON PILA NO DETERMINISTA

Un autómata finito con pila no determinista (AFPN) consta de los mismos parámetros de un AFPD.

P = (Q, Σ, Г, Δ, q0, T,Z):

Donde la función de transición Δ es de la forma:

       Δ: Q × (Σ U { ε }) × Г→ Pf(Q × Г*)

Donde Pf (Q× Г *) es un conjunto de subconjuntos finitos de Q × Г*

Para q є Q, a є Σ U {ε} y s є Г

       Δ (q, a, s) = {(q1, γ1), (q2, γ 2), . . . , (qn, γ n)}

Donde γi є Г*