Automatas finitos

AUTÓMATAS FINITOS

 Autómatas finitos reconocen los lenguajes regulares y, por el contrario, cualquier idioma, que es reconocido por un autómata finito es regular. Existen otros tipos de autómatasfinitos como los autómatas finitos no deterministas y autómatas no deterministas.
Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre unalfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si lasecuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final.
Condiciones de estado de transición
Estado
Condiciones de salida.
INPUTS
OUTPUTS
Sipara todo estado del autómata existe como máximo una transición definida para cada símbolo del alfabeto, se dice que el autómata es determinantico (AFD). Si a partir de algún estado y para el mismosímbolo de entrada, se definen dos o más transiciones se dice que el autómata es no determinantico (AFND).
Formalmente un autómata finito se define como una 5-upla
M= (Q, Σ, q0, δ, F) donde:
* es unconjunto finito de estados;
* es un alfabeto finito;
* es el estado inicial;
* es una función de transición;
* es un conjunto de estados finales o de aceptación.

En el comienzo del proceso dereconocimiento de una cadena de entrada, el autómata finito se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va cambiando de estado de acuerdo a lo determinado por lafunción de transición. Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es unestado de aceptación, entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.
Note que el estado inicial de un autómata finito...