Colas

AUTOMATA

DEFINICION:

Un autómata es un modelo matemático para una máquina de estado finita (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a travésde una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estadocambiar dados unos determinados estados y símbolos.

SE CLASIFICAN COMO:

Autómata con pila

Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema querecibe una cadena constituida 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 delos 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  donde:
* Σ y  son alfabetos de entrada, dela cadena y de la pila respectivamente;
* 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 ofinales.
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 si apiláramos platos uno encima de otro, y naturalmente elprimero que quitaremos es el último que hemos colocado.

AUTOMATAS FINITOS (AF)

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en formaautomática sobre una entrada para producir una salida.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa enuna función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se...