Autómatas finitos
Los autómatas pueden ser deterministas AFD o no deterministas AFN.
Se distinguen por la naturaleza de sus transiciones.
- AFD:
- Una sola transición: Para cada estado y entrada, hay exactamente una transición a un nuevo estado.
- Determinístico: El siguiente estado está completamente determinado por el estado actual y la entrada.
- AFN:
- Múltiples transiciones: Desde un estado y una entrada, pueden existir múltiples transiciones posibles a diferentes estados.
- No determinista: El siguiente estado no siempre está completamente determinado, hay un elemento de elección.
Sin embargo, hay autómatas que se clasifican por el momento en que se produce la salida.
- Moore:
- Salida asociada al estado: La salida de un autómata de Moore está asociada exclusivamente con el estado en el que se encuentra. Es decir, la salida depende solo del estado actual y no de la entrada que lo causó.
- Respuesta retardada: La salida puede considerarse una respuesta "retardada" a la entrada, ya que refleja el estado en el que el autómata se encuentra después de procesar la entrada.
- Mealy:
- Salida asociada a la transición: La salida de un autómata de Mealy está asociada con la transición entre estados. Es decir, la salida depende tanto del estado actual como de la entrada que provoca el cambio de estado.
- Respuesta inmediata: La salida puede considerarse una respuesta "inmediata" a la entrada, ya que se produce en el momento en que se realiza la transición.
Definición de autómatas de Mealy y Moore
Autómata de Mealy
Un autómata de Mealy es una séxtupla ( (Q, q_0, V_T, S, f, g) ), donde:
- ( Q ): Es el conjunto de estados.
- ( q_0 ): Es un elemento de ( Q ) que se considera el estado inicial.
- ( V_T ): Es el conjunto de símbolos de entrada (estímulos).
- ( S ): Es el conjunto de elementos de salida (respuestas).
- ( f ): Es la función que define los cambios de estado según las entradas, ( f : Q \times V_T \to Q ).
- ( g ): Es la función que genera las salidas en función de los estados y las entradas, ( g : Q \times V_T \to S ).
Autómata de Moore
Un autómata de Moore es una séxtupla ($Q, q_0, V_T, S, f, g$), igual al autómata de Mealy salvo que:
- La función ( g ) se consautomataidera definida del conjunto ( Q ) en ( S ), es decir, ( g : Q \to S ).
La diferencia principal entre un autómata de Mealy y uno de Moore es que:
- En el autómata de Mealy, las respuestas se asocian a las transiciones (los arcos del grafo).
- En el autómata de Moore, las respuestas se asocian a los estados (los nodos del grafo).
Los autómatas finitos se corresponden a una Gramática (Autómata).