Autómata con pila

Autómata con pila
Un autómata con pila o autómata de pila o autómata a pila o autómata apilador es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto ydetermina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata a pila pertenece al grupo de los lenguajes de contexto libre en la clasificación de laJerarquía de Chomsky.
Definición formal
Formalmente, un autómata con pila puede ser descrito como una séptupla M = (S,Σ,Γ,δ,s,Z,F) donde:
* Σ y Γ son alfabetos de entrada, de la cadena y de la pilarespectivamente;
* S un conjunto de estados;
*
* es el estado inicial;
* es el símbolo inicial de la pila;
* es un conjunto de estados de aceptación o finales.
La interpretaciónde con es la siguiente:
Cuando el estado del autómata es s, el símbolo que la cabeza lectora está inspeccionando en ese momento es a, y en la cima de la pila nos encontramos el símbolo Z, se realizanlas siguientes acciones:
* Si , es decir no es la palabra vacía, se avanza una posición la cabeza lectora para inspeccionar el siguiente símbolo.
* Se elimina el símbolo Z de la pila delautómata.
* Se selecciona un par (pi,γi) de entre los existentes en la definición de δ(s,A,Z), la función de transición del autómata.
* Se apila la cadena en la pila del autómata, quedando elsímbolo A1 en la cima de la pila.
* Se cambia el control del autómata al estado pi.
Ejemplo
Sea el siguiente lenguaje libre del contexto ; formado por las cadenas
Dicho lenguaje puede serreconocido por el siguiente autómata con pila:

donde las transiciones son:

para cualquier (q,θ,ρ)
El significado de las transiciones puede ser explicado analizando la primera transición:

donde q0 esel estado actual, a es el símbolo en la entrada y ε se extrae de la cima de la pila. Entonces, el estado del automata cambia a q1 y el símbolo se coloca en la cima de la pila.
La idea del...