Automatas Finitos

AUTOMATAS FINITOS
Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto 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 la secuencia de transiciones correspondientes a los símbolos de xconduce desde el estado inicial a un estado final.
Si para 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 mismo sí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 definecomo una 5-upla
M= (Q, Σ, q0, δ, F) donde:
* es un conjunto 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.
Funcionamiento
En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata finito se encuentra en el estado inicial y a medida que procesacada símbolo de la cadena va cambiando de estado de acuerdo a lo determinado por la funció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 un estado de aceptación, entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadenano pertenece a dicho lenguaje.
Note que el estado inicial de un autómata finito siempre es único, en tanto que los estados finales pueden ser más de uno, es decir, el conjunto puede contener más de un elemento. También puede darse el caso de que un estado final corresponda al mismo estado inicial.
Representación como diagramas de estados
Este autómata finito está definido sobre el alfabetoΣ={0,1}, posee dos estados s1 y s2, y sus transiciones son δ(s1,0)=s2, δ(s1,1)=s1, δ(s2,0)=s1 y δ(s2,1)=s2. Su estado inicial es s1, que es también su único estado final.
Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
* Los estados se representan como vértices, etiquetados con su nombre en elinterior.
* Una transición desde un estado a otro, dependiente de un símbolo del alfabeto, se representa mediante una arista dirigida que une a estos vértices, y que está etiquetada con dicho símbolo.
* El estado inicial se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.
* El o los estados finales se representan mediante vértices que están encerrados a suvez por otra circunferencia.

AUTÓMATA FINITO DETERMINISTA
(AFD)

Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, F) donde:
Q es un conjunto de estados;
Σ es un alfabeto;
q0 es el estado inicial;
δ es una función de transición;
F es un conjunto de estados finales o de aceptación.
Este se representa a través de un diagrama que tiene forma de grafo dirigido coninformación adicional añadida, y se llama diagrama de transición.
Los nodos del grafo se llaman estados y se usan para señalar, en ese momento, hasta qué lugar se ha analizado la cadena.
Las aristas del grafo se etiquetan con caracteres del alfabeto y se llaman transiciones.
Si el siguiente carácter a reconocer concuerda con la etiqueta de alguna transición que parta del estado actual, nos desplazamosal estado que nos lleve la arista correspondiente.
Naturalmente, nosotros debemos de comenzar por un estado inicial, y cuando se hayan tratado todos los caracteres de la cadena correspondiente, necesitamos saber si la cadena es legal.
Para ello se marcan ciertos estados como estados de aceptación o estados finales.
Si cuando ha sido tratada la cadena en su totalidad terminamos en un estado...