Máquina de estados finitos
Una máquina de estados finitos ( FSM ) o autómatas de estados finitos ( FSA , plural: autómatas ), autómatas finitos , o simplemente una máquina de estados , es un modelo matemático de cálculo . 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]Un FSM se define por una lista de sus estados, su estado inicial y las entradas que desencadenan cada transición. Máquinas de estado finito son de dos tipos: las máquinas de estados finitos deterministas y máquinas de estados finitos no deterministas . [2] Se puede construir una máquina determinista de estados finitos equivalente a cualquier 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 en función de una secuencia de eventos con los que se presentan. Ejemplos simples 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 autos 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 potencia computacional significa que hay tareas computacionales que una máquina de Turing puede hacer pero una FSM no. Esto se debe a que la memoria de un 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 sólo puede realizar operaciones de "lectura" y siempre tiene que moverse de izquierda a derecha. Los 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 usa para controlar el acceso al metro y los juegos mecánicos del parque de diversiones, es una puerta con tres brazos giratorios a la altura de la cintura, uno a través de la entrada. Inicialmente, los brazos están bloqueados, bloqueando la entrada e impidiendo el paso de los clientes. Al depositar una moneda o ficha en una ranura del torniquete, se desbloquean los brazos, lo que permite que un solo cliente avance. Después de que el cliente pasa, los brazos se bloquean nuevamente hasta que se inserta otra moneda.
Considerado como una máquina de estados, el torniquete tiene dos estados posibles: bloqueado y desbloqueado . [4] Hay dos entradas posibles que afectan su estado: poner una moneda en la ranura ( moneda ) y empujar el brazo ( empujar ). En el estado bloqueado, empujar el brazo no tiene ningún efecto; no importa cuántas veces se dé el impulso de 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 ningún efecto; es decir, dando una 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 (según las entradas dadas a la máquina) y las salidas resultantes de cada entrada:
