INTRODUCCIÓN Las funciones que desempaña una maquina de estado finito es un factor importante debido a que tienen un campo muy amplio de aplicación, cada uno de los elementos que se requieren para que estas maquinas desempeñen funciones necesarias e importantes.
Una maquina de estado finito o maquina secuencial es un sistema N=(I,S,O,δ,ʎ) donde:
I: alfabeto que representan los símbolos de entrada.
S: representación de los estados que componen la maquina.
O: alfabeto que representa los símbolos de salida. δ: transformación de SXI (función de estado siguiente)
ʎ: Transformación de SXI (función de salida).
Se supone que la maquina esta en un estado inicial S.
Modelo de una maquina de estado finito
La maquina lee una secuencia de símbolos de entrada que están almacenados en una cinta de entrada y almacena una secuencia de símbolos de salida en una cinta de salida. Supóngase que la maquina se encuentra en un estado SI y que lee sus símbolos de entrada a1 en una cabeza de lectura. Se aplica entonces la transformación l causando así que la cabeza de escritura registre un símbolo ok en la cinta de la salida. La función d hace que la maquina entre en el estado SJ. La maquina procede a leer el siguiente símbolo de entrada y continua su operación hasta que se hayan procesado todos los símbolos en la cinta de entrada. Ejemplo: lo siguiente define una maquina de estado finito con 2 símbolos de entrada, 3 estados internos y 3 símbolos de salida.
I={a,b} S={q0,q1,q2} O={x,y,z}
=función de próximo estado SXI (q0,a)=q1 (q1,a)=q2 (q2,a)=q0 (q0,b)=q2 (q1,b)=q1 (q2,b)=q1 = función de salida SXI=O definida por: (q0,a)=x (q1,a)=x (q2,a)=z (q0,b)=y (q0,b)=z (q2,b)=y
NOTA: es tradicional usar la letra q para los estados de la maquina y usar el símbolo q0 para el estado inicial.
Ontiveros Bemejo Brenda Shantal 302