Maquina de estado finito

Maquina de estado finito

Máquina de estados finitos python

Introducción de los autómatas finitosLos autómatas finitos (FA) son la máquina más sencilla para reconocer patrones. El autómata finito o máquina de estados finitos es una máquina abstracta que tiene cinco elementos o tuplas. Tiene un conjunto de estados y reglas para pasar de un estado a otro, pero depende del símbolo de entrada aplicado. Básicamente, es un modelo abstracto de un ordenador digital. La siguiente figura muestra algunas características esenciales de los autómatas finitos.Figura: Características de los autómatas finitosLa figura anterior muestra las siguientes características de los autómatas:Un autómata finito consta de lo siguiente :  Q : Conjunto finito de estados.

δ : Función de transición, definida como δ : Q X Σ –> Q.En un DFA, para un carácter de entrada particular, la máquina va a un solo estado. Una función de transición se define en cada estado para cada símbolo de entrada. También en el DFA el movimiento nulo (o ε) no está permitido, es decir, el DFA no puede cambiar de estado sin ningún carácter de entrada.  Por ejemplo, el siguiente DFA con Σ = {0, 1} acepta todas las cadenas que terminan en 0. Figura: DFA con Σ = {0, 1} Una cosa importante a tener en cuenta es que puede haber muchos DFAs posibles para un patrón. Un DFA con un número mínimo de estados es generalmente preferido.  2) Autómatas Finitos No Deterministas (NFA) NFA es similar a DFA excepto las siguientes características adicionales:  Sin embargo, estas características anteriores no añaden ninguna potencia al NFA. Si comparamos ambos en términos de potencia, ambos son equivalentes.  Debido a las características adicionales anteriores, NFA tiene una función de transición diferente, el resto es el mismo que DFA.  δ: Función de transición

Diseñador de máquinas de estado finito

Sabemos que los circuitos secuenciales síncronos cambian (afectan) sus estados por cada transición positiva (o negativa) de la señal de reloj en función de la entrada. Por lo tanto, este comportamiento de los circuitos secuenciales síncronos puede ser representado en forma gráfica y se conoce como diagrama de estado.

Como se muestra en la figura, hay dos partes presentes en la máquina de estado de Mealy. Estas son la lógica combinacional y la memoria. La memoria es útil para proporcionar algunas o parte de las salidas anteriores (estados actuales) como entradas de la lógica combinacional.

En la figura anterior, hay tres estados: A, B y C. Estos estados están etiquetados dentro de los círculos y cada círculo corresponde a un estado. Las transiciones entre estos estados se representan con líneas dirigidas. Aquí, 0 / 0, 1 / 0 y 1 / 1 denotan entrada / salida. En la figura anterior, hay dos transiciones de cada estado basadas en el valor de la entrada, x.

En general, el número de estados requeridos en la máquina de estado Mealy es menor o igual al número de estados requeridos en la máquina de estado Moore. Hay una máquina de estado de Moore equivalente para cada máquina de estado de Mealy.

Diseño lógico digital de máquinas de estado finito

Ejemplo de autómata finito determinista que sólo acepta números binarios múltiplos de 3. El estado S0 es a la vez el estado inicial y un estado de aceptación. Por ejemplo, la cadena «1001» conduce a la secuencia de estados S0, S1, S2, S1, S0, y por tanto es aceptada.

En la teoría de la computación, una rama de la informática teórica, un autómata finito determinista (DFA) -también conocido como aceptador finito determinista (DFA), máquina de estado finito determinista (DFSM) o autómata de estado finito determinista (DFSA)- es una máquina de estado finito que acepta o rechaza una cadena de símbolos dada, recorriendo una secuencia de estados determinada únicamente por la cadena[1]. En busca de los modelos más simples para capturar las máquinas de estado finito, Warren McCulloch y Walter Pitts fueron de los primeros investigadores en introducir un concepto similar al de autómata finito en 1943[2][3].

La figura ilustra un autómata finito determinista mediante un diagrama de estados. En este autómata de ejemplo, hay tres estados: S0, S1 y S2 (denotados gráficamente por círculos). El autómata toma como entrada una secuencia finita de 0s y 1s. Para cada estado, hay una flecha de transición que lleva a un siguiente estado tanto para 0 como para 1. Al leer un símbolo, un DFA salta determinísticamente de un estado a otro siguiendo la flecha de transición. Por ejemplo, si el autómata está actualmente en el estado S0 y el símbolo de entrada actual es 1, entonces salta determinísticamente al estado S1. Un DFA tiene un estado de inicio (denotado gráficamente por una flecha que viene de ninguna parte) donde comienzan los cálculos, y un conjunto de estados de aceptación (denotados gráficamente por un círculo doble) que ayudan a definir cuando un cálculo es exitoso.

Ejemplos de máquinas de estado finito en la vida real

Una máquina de estado finito (FSM) o autómata de estado finito (FSA, plural: autómatas), 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 cualquier momento. La FSM puede cambiar de un estado a otro en respuesta a algunas entradas; el cambio de un estado a otro se denomina 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 estado finito son de dos tipos: máquinas de estado finito deterministas y máquinas de estado finito no deterministas[2] Una máquina de estado finito determinista puede construirse de forma 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 en función de una secuencia de eventos que se les presenta. 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 viene determinada por los pisos solicitados por los usuarios, los semáforos, que cambian de secuencia cuando los coches están esperando, y las cerraduras de combinación, que requieren la introducción de una secuencia de números en el orden adecuado.

Entradas relacionadas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad