Automatas Finitos

Autómatas Finitos Deterministas
Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automá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 en una función de transición, que recibe a partir de unestado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según laJerarquía de Chomsky.
Definicion Formal
Formalmente, un autómata finito es una 5-tupla (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, elautó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 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 allenguaje 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 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 diagramasde estados

Ilustración [ 1 ]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 siguientemanera:
* Los estados se representan como vértices, etiquetados con su nombre en el interior.
* 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 su vez por otra circunferencia

Representación como tabla de transiciones
Otra manera de describir el funcionamiento de un autómata finito es mediante el uso de tablas de transiciones o matrices de estados. Dos posibles tablas para el ejemplo de la imagen anterior podrían ser las siguientes:
salida
q ∈ Q| símbolo
σ ∈ Σ | llegada
δ(q,σ) ∈ Q |
s1 | 0 | s2 |
s1 | 1 | s1 |
s2 | 0 | s1 |
s2 | 1 | s2 |
| | 0 | 1 |
→*s1 | s2 | s1 |
s2 | s1 | s2 |

|
La primera representa explícitamente los parámetros y el valor que toma cada ocurrencia de la función de transición. La segunda es más compacta, y marca con una flecha el estado inicial, y con un asterisco los estados finales.
Autómatafinito determinista

Ilustración [ 2 ]AFD que reconoce el lenguaje regular
conformado exclusivamente por las cadenas con
un número par de ceros y par de unos.

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído,...