Maquinas de estado finito MEF

AUTOMATAS FINITOS (Maquinas de estado finito MEF)

Las máquinas de estado finito son una herramienta muy útil para especificar aspectos relacionados con tiempo real, dominios reactivos o autónomos, computación reactiva, protocolos, circuitos, arquitecturas de software, etc.

Máquina de estado finito es un modelo matemático 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.

Una MEF consta de:

M= (I,O,S,F,G)

I=  conjunto finito de simbolos de entrada

O= conjunto finito  de simbolos de salida

S= conjunto finito de estados

F= función de estado siguiente S * I  en S

G= función de salida de S *I en O

= estado inicial

1. Encuentre el diagrama de transición de una máquina de estado finito:   

I  = {a, b}

O= {0, 1}

S= { 0, 1, 2 }

Funciones de Estado siguiente:

F ( 0, a) = 2

F ( 0, b) = 0

F ( 1, a)= 1

F ( 1, b)= 1

F ( 2, a)= 0

F ( 2, b)= 1

Funciones de salida.                                                   

G ( 0 ,a)=1                                                           

G ( 1 ,a)=1                                                           

G ( 1 ,b)=1

G ( 2,a)=0

G ( 2 ,b)=1

2. Encuentre el diagrama de transición de una máquina de estado finito:

   



I  = {a, b}

O= {0, 1}

S= { 0, 1}

Funciones de Estado siguiente:

F ( 0, a) = 1

F ( 0, b) = 0

F ( 1, a) = 0

F ( 1, a) = 0

Funciones de salida.                                                   

G ( 0, a)=0                                               

G ( 0, b)=1                                                           

kG ( 1, a)=1

G ( 1, b)=1

Diagrama de transición: