Máquina de estados finitos
Una máquina de estado finito ( FSM ) o autómata de estado finito ( FSA , plural: automata ), autómata finito , o simplemente una máquina de estado , es un modelo matemático de computación . Es una máquina abstracta que puede estar exactamente en uno de un número finito de estados en un momento dado. El FSM puede cambiar de un estado a otro en respuesta a algunas entradas ; el cambio de un estado a otro se llama transición . [1]Una FSM se define mediante una lista de sus estados, su estado inicial y las entradas que desencadenan cada transición. Las máquinas de estados finitos son de dos tipos : máquinas deterministas de estados finitos y máquinas no deterministas de estados finitos . [2] Se puede construir una máquina determinista de estados finitos equivalente a cualquier máquina no determinista.
El comportamiento de las máquinas de estado se puede observar en muchos dispositivos de la sociedad moderna que realizan una secuencia predeterminada de acciones dependiendo de la secuencia de eventos que se les presentan. Ejemplos sencillos son las máquinas expendedoras , que dispensan productos cuando se deposita la combinación adecuada de monedas, los ascensores , cuya secuencia de paradas está determinada por los pisos solicitados por los pasajeros, los semáforos , que cambian de secuencia cuando los automóviles están esperando, y las cerraduras de combinación , que requieren la entrada de una secuencia de números en el orden correcto.
La máquina de estados finitos tiene menos poder computacional que algunos otros modelos de computación como la máquina de Turing . [3] La distinción de poder computacional significa que hay tareas computacionales que una máquina de Turing puede hacer pero una FSM no puede. Esto se debe a que la memoria de una FSM está limitada por el número de estados que tiene. Una máquina de estados finitos tiene el mismo poder computacional que una máquina de Turing que está restringida de tal manera que su cabeza solo puede realizar operaciones de "lectura" y siempre tiene que moverse de izquierda a derecha. Las FSM se estudian en el campo más general de la teoría de autómatas .
Un ejemplo de un mecanismo simple que puede ser modelado por una máquina de estado es un torniquete . [4] [5] Un torniquete, que se utiliza para controlar el acceso al metro y las atracciones del parque de diversiones, es una puerta con tres brazos giratorios a la altura de la cintura, uno cruzando la entrada. Inicialmente, los brazos están bloqueados, bloqueando la entrada e impidiendo el paso de los clientes. Depositar una moneda o una ficha en una ranura del torniquete desbloquea los brazos, lo que permite que un solo cliente pase. Después del paso del cliente, los brazos se bloquean nuevamente hasta que se inserta otra moneda.
Considerado como una máquina de estados, el torniquete tiene dos posibles estados: Bloqueado y Desbloqueado . [4] Hay dos posibles entradas que afectan a su estado: poner una moneda en la ranura ( moneda ) y empujar el brazo ( push ). En el estado bloqueado, empujar el brazo no tiene efecto; no importa cuántas veces se presione la entrada , permanece en el estado bloqueado. Poner una moneda, es decir, darle a la máquina una entrada de moneda , cambia el estado de Bloqueado a Desbloqueado . En el estado desbloqueado, poner monedas adicionales no tiene efecto; es decir, dando moneda adicionalentradas no cambia el estado. Sin embargo, un cliente empujando a través de los brazos, dando una entrada de empuje , cambia el estado de nuevo a Bloqueado .
La máquina de estado del torniquete se puede representar mediante una tabla de transición de estado , que muestra para cada estado posible, las transiciones entre ellos (basadas en las entradas dadas a la máquina) y las salidas resultantes de cada entrada:
