Se denomina máquina de estados a un modelo de comportamiento de un sistema con entradas y salidas, en donde las salidas dependen no sólo de las señales de entradas actuales sino también de las anteriores. Las máquinas de estados se definen como un conjunto de estados que sirve de intermediario en esta relación de entradas y salidas, haciendo que el historial de señales de entrada determine, para cada instante, un estado para la máquina, de forma tal que la salida depende únicamente del estado y las entradas actuales.
Una máquina de estados se denomina máquina de estados finitos (FSM por finite state machine) si el conjunto de estados de la máquina es finito, este es el único tipo de máquinas de estados que podemos modelar en un computador en la actualidad; debido a esto se suelen utilizar los términos máquina de estados y máquina de estados finitos de forma intercambiable. Sin embargo un ejemplo de una máquina de estados infinitos seria un computador cuántico esto es debido a que los Qubit que utilizaría este tipo de computadores toman valores continuos, en contraposición los bits toman valores discretos (0 ó 1). Otro buen ejemplo de una máquina de estados infinitos es una Máquina universal de Turing la cual se puede definir teóricamente con una "cinta" o memoria infinita.
La representación de una máquina de estados se realiza mediante un Diagrama de estados, sin embargo también es posible utilizar un Diagrama de flujo.
Es posible clasificar las máquinas de estados en aceptoras o transductoras:
La máquina 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 máquina procede a leer el siguiente símbolo de entrada y continúa su operación hasta que se hayan procesado todos los símbolos en la cinta de entrada.
Ejemplo:
lo siguiente define una máquina 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}
Las Máquinas de Estados Finitos (FSM), también conocidas como Autómatas de Estados Finitos (FSA), explicado de forma simple, son modelos de comportamiento de un sistema o un objeto complejo, con un número limitado de modos o condiciones predefinidos, donde existen transiciones de modo.
Las FSMs están compuestas por 4 elementos principales:
· estados que definen el comportamiento y pueden producir acciones
· transiciones de estado que son movimientos de un estado a otro
· reglas o condiciones que deben cumplirse para permitir un cambio de estado
· eventos de entrada que son externos o generados internamente, que permiten el lanzamiento de las reglas y permiten las transiciones
Una máquina de estados finitos debe tener un estado inicial que actúa de punto de comienzo, y un estado actual que recuerda el producto de la anterior transición de estado. Los eventos recibidos como entrada actúan como disparadores, que causan una evaluación de las reglas que gobiernan las transiciones del estado actual a otro estado. La mejor manera de visualizar una FSM es pensar en ella como un diagrama de flujo o un grafo dirigido de estado, aunque como se verá existen técnicas de abstracción más precisas que pueden ser usadas.
OBJETIVO
Analizar los elementos que forman una máquina de estado finito, así como su función.
JUSTIFICACIÓN
El analizar este tema nos llevara a un mejor entendimiento del comportamiento de algunos dispositivos de computación y electrónicos como lo pueden ser cajeros automáticos.
INTRODUCCIÓN
Las funciones que desempaña una máquina 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 máquinas desempeñen funciones necesarias e importantes.
CONTENIDO
Una máquina 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. |
