Automatas De Pila Y LLC

Autómata
Al igual que con los lenguajes regulares podemos definir un autómata
como una maquina reconocedora de cadenas (palabras) de un
determinado lenguaje.
Son dispositivos de computo que operancomo una maquina de estados
finitos, las cuales realizan un encadenamiento automático y continuo de
operaciones capaces de procesar una información de entrada para
producir otra de salida.
Por logeneral los autómatas finitos no son lo suficientemente poderosos
para aceptar el control de enlace lógico LLC (Logical Link Control) quien es
el que define la forma en que los datos son transferidos sobreel medio
físico, proporcionando servicio a las capas superiores

El punto fue agregar “algo” a los Autómatas Finitos para que de alguna manera se
incremente.
Por tal motivo surgen los Autómatas dePila, que al igual que un
Autómata Finito, cuenta con un flujo de entrada y un flujo de control
que puede encontrarse en uno de entre un número finito de estados, uno de estos
estados se designa como elinicial y por lo menos un estado de aceptación
La principal diferencia es que los Autómatas de pila cuentan justamente con una pila
en donde se puede almacenar información para recuperarla mástarde.

Los símbolos que pueden almacenarse en esta pila se conocen
como símbolos de pila de la maquina, constituyen un conjunto
finito que puede incluir algunos símbolos definiendo el alfabeto
de lamaquina y quizá algunos símbolos adicionales que se
utilizan como marcas internas.
Si una maquina inserta un símbolo especial en la pila antes de
efectuar algún otro cálculo, entonces ese símbolo en lacima de
la pila puede usarse como indicador de pila vacía.

Características
La Pila funciona de manera que el último carácter que se almacena en ella es el
primero en salir (orden LIFO), como siapiláramos platos uno encima de otro, y
naturalmente el primero que quitaremos es el último que hemos colocado.
Un aspecto crucial de la pila es que sólo podemos modificar el“tope”de la pila,
que es el...