3.1 - Conceptos: Definición y Clasificación de Autómata Finito (AF).

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 un estado 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.

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.

CLASIFICACIÓN DE AF LOS AUTÓMATAS SE PUEDEN CLASIFICAR EN:

· Deterministas; Cada combinación (estado, símbolo de entrada) produce un solo estado.

· No Deterministas; Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

Los autómatas se pueden representar mediante tablas de transición o diagramas de transición.

EJEMPLO: 

Ejemplo: Sea el AFD1 = ({a,b}, {p,q,r}, f, p, {q}) donde f está

definida por:
f(p,a) = q f(p,b) = r
f(q,a) = q f(q,b) = r
f(r,a) = r f(r,b) = r

Escribir su tabla de transición y dibujar su diagrama de transición.
estados (Q): p, q, r
estado inicial: p
estado final: q

Diagramas de transición:

• Nodos etiquetados por los estados(Q)
• Arcos entre nodos etiquetados con ( E )
• Q0 se señala con ->
• El estado final se señala con * o con doble circulo