Autómata finito

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

Definición formal

Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla (S,Σ,T,s,A) donde: 

    * S un conjunto de estados;
    * Σ es un alfabeto;
    * T es la función de transición: 
    * s \in S es el estado inicial;
    * A \subseteq S es un conjunto de estados de aceptación o finales.

Ejemplo 1 

    * S = {S1, S2},
    * Σ = {0,1},
    * T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})}
    * s = S1
    * A = {S1}.

Google