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: ;
• es el estado inicial;
• es un conjunto de estados de aceptación o finales.

Ejemplo 1

• S = {S₁, S₂},
• Σ = {0,1},
• T = {(S₁,0,{S₂});(S₁,1,{S₁});(S₂,0,{S₁});(S₂,1,{S₂})}
• s = S₁
• A = {S₁}.

Formas de representar un autómata finito

Además de notar un AF a través de su definición formal es posible representarlo a través de otras notaciones que resultan más cómodas. Entre estas notaciones, las más usuales son:

• Las Tablas de Transiciones: la tabla de transición para el AF del ejemplo 1 es

	0	1
S1	S2	S1
S2	S1	S2

• Los Diagramas de Transiciones: el diagrama de transición para el AF del ejemplo 1 es

• Las Expresiones regulares. Se demuestra que dado un autómata de estados finitos, existe una expresión regular que lo representa.

Ø υ 1* υ (1* ο 0 ο 1* ο 0)*

Más información en:

http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito#Definici.C3.B3n_formal