Autómatas Finitos

Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final.
Si para todo estado del autómata existe como máximo una transición definida para cada símbolo del alfabeto, se dice que el autómata es determinístico (AFD). Si a partir de algún estado y para el mismo símbolo de entrada, se definen dos o más transiciones se dice que el autómata es no determinístico (AFND).
Formalmente un autómata finito se define como una 5-upla:


 

Función de transición para cadenas

 

Equivalencia entre AFD y AFND

 

Minimización de AFD
Para cada AFD existe un AFD con cantidad mínima de estados que acepta el mismo lenguaje.
El algoritmo de minimización divide el conjunto de estados del AFD en clases de equivalencia. Los pasos a seguir son los siguientes:

 

Construcción del AFND a partir del AFND-
Dado un AFND- es posible construir un  AFND equivalente sin transiciones vacías que reconoce el mismo lenguaje.
Los estados del nuevo autómata son los estados importantes del AFND- y el estado inicial del AFND-. Se denominan estados importantes aquellos estados a los que llega un arco con un símbolo real como rótulo.
El estado inicial es el estado inicial del AFND-.
La función de transición se define teniendo en cuenta que existe una transición del estado importante ei al estado importante ej con el símbolo x, si existe algún estado ek tal que:
    - se puede llegar desde el estado ei al estado ek con un camino de 0 ó mas transiciones ; se permite ei = ek;
    - en el AFND- existe una transición del estado ek al estado ej rotulada con el símbolo x.
Los estados finales del nuevo autómata son los estado finales del AFND- y todos los estados ei del AFND- para los cuales existe un camino con transiciones , en el AFND-, a algún estado final del AFND-.
 

Autómata finito: Modelo

 

Autómata Finito Traductor


 

Función de traducción para cadenas