bases de datos

Lenguajes y automatas 1
















OBJETIVO
Ver como se puede realizar un autómata de pila, en que consiste, lo que significa, como es que trabaja cada transición lo que esun estado, hacia donde se puede dirigir y que es lo que lo hace avanzar, retroceder o quedarse en el mismo lugar, sus estados iníciales y finales, esto aplicarlo a la programación, con un programa endonde te diga las transiciones que realiza la cadena que introduzcas y si la cadena es aceptada por el AP, si saca o mete a la pila, si la lee, y si cumple con el grafo para que pueda ser leída.MARCO TEORICO
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 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 con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de laJerarquía de Chomsky.
Formalmente, un autómata con pila puede ser descrito como una séptupla donde:
Σ y son alfabetos de entrada, de la cadena y de la pila respectivamente;
S un conjunto deestados;

es el estado inicial;
es el símbolo inicial de la pila;
es un conjunto de estados de aceptación o finales.

La interpretación de con es la siguiente:
Cuando el estado del autómata es , elsímbolo que la cabeza lectora está inspeccionando en ese momento es , y en la cima de la pila nos encontramos el símbolo , se realizan las siguientes acciones:
Si , es decir no es la palabra vacía, seavanza una posición la cabeza lectora para inspeccionar el siguiente símbolo.
Se elimina el símbolo Z de la pila del autómata.
Se selecciona un par de entre los existentes en la definición de , lafunción de transición del autómata.
Se apila la cadena en la pila del autómata, quedando el símbolo en la cima de la pila.
Se cambia el control del autómata al estado .
Funcionamiento
Los...