La teoría de autómata

La teoría de autómatas 

Es una rama de la teoría de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer. También son de gran utilidad en la teoría de la complejidad computacional.

Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de 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é estado cambiar dados unos determinados estado y símbolo.

Leyes y algoritmos

Definición formal

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.

En un AFD no pueden darse ninguno de estos dos casos:

Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;

Que existan transiciones del tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transiciones hacia otros estados.

Procesamiento de las cadenas de un AFD

Sea A AFD y w = a1a2 −−− an una cadena de entrada para A.

Iniciamos con A en su estado q0, δ(q0, a1) = q1.

Procesamos a2, δ(q1, a2) = q2 y continuamos encontrando q3, q4, . . . , qn. δ(qi1, ai) = qi para cada i.

Si qn 2 F diremos que la entrada w = a1a2 −−− an es aceptada sino es rechazada

Ejemplo

El siguiente ejemplo es de un DFA M , con un alfabeto binario, que requiere que la entrada contenga un número par de 0.

M = ( Q , Σ, δ, q 0 , F ) donde

·        Q = { S 1 , S 2 },

·        Σ = {0, 1},

·        q 0 = S 1 ,

·        F = { S 1 }, y

·        δ se define mediante la siguiente tabla de transición de estado: