Máquina de estados finitos

Clases de autómatas

En informática teórica , una máquina de estados finitos ( MEF ), autómata de estados finitos ( AEF ) , o simplemente máquina de estados , es un modelo matemático de computación . ^[¹^] Es una máquina abstracta que puede estar en exactamente uno de un número finito de estados en un momento dado. La MEF puede cambiar de un estado a otro en respuesta a ciertas entradas ; este cambio se denomina transición . ^[²^] Una MEF se define mediante una lista de sus estados, su estado inicial y las entradas que desencadenan cada transición. Existen dos tipos de máquinas de estados finitos: deterministas y no deterministas . ^[³^]^[⁴^] Para cualquier máquina de estados finitos no determinista, se puede construir una equivalente determinista. ^[⁵^]

El comportamiento de las máquinas de estados 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 presentan. Ejemplos sencillos son las máquinas expendedoras , que dispensan productos cuando se deposita la combinación correcta de monedas; los ascensores , cuya secuencia de paradas está determinada por los pisos solicitados por los usuarios; los semáforos , que cambian de secuencia cuando hay coches esperando; y las cerraduras de combinación , que requieren la introducción de una secuencia de números en el orden correcto.

La máquina de estados finitos tiene menor potencia computacional que otros modelos de computación, como la máquina de Turing . ^{[ 6 ]} Esta diferencia en la potencia computacional implica que existen tareas computacionales que una máquina de Turing puede realizar, pero una máquina de estados finitos no. Esto se debe a que la memoria de una máquina de estados finitos está limitada por el número de estados que posee. Una máquina de estados finitos tiene la misma potencia computacional que una máquina de Turing, pero con la restricción de que su cabezal solo puede realizar operaciones de "lectura" y siempre debe moverse de izquierda a derecha. Las máquinas de estados finitos se estudian en el campo más general de la teoría de autómatas .

Ejemplo: torniquete que funciona con monedas

Un ejemplo de mecanismo simple que puede modelarse mediante una máquina de estados es un torniquete . ^{[ 7 ]}^{[ 8 ]} Un torniquete, utilizado para controlar el acceso al metro y a las atracciones de los parques de diversiones, es una puerta con tres brazos giratorios a la altura de la cintura, uno de ellos en la entrada. Inicialmente, los brazos están bloqueados, impidiendo el paso a los usuarios. Al introducir una moneda o ficha en una ranura del torniquete, los brazos se desbloquean, permitiendo el paso a un solo usuario. Una vez que el usuario pasa, los brazos se bloquean de nuevo hasta que se inserta otra moneda.

Considerado como una máquina de estados, el torniquete tiene dos estados posibles: Bloqueado y Desbloqueado . ^{[ 7 ]} Hay dos entradas posibles que afectan su estado: colocar una moneda en la ranura ( moneda ) y empujar el brazo ( empujar ). En el estado bloqueado, empujar el brazo no tiene efecto; no importa cuántas veces se dé la entrada empujar , permanece en el estado bloqueado. Colocar una moneda, es decir, dar a la máquina una entrada de moneda , cambia el estado de Bloqueado a Desbloqueado . En el estado desbloqueado, colocar monedas adicionales no tiene efecto; es decir, dar entradas de monedas adicionales no cambia el estado. Un cliente empujando a través de los brazos da una entrada empujar y restablece el estado a Bloqueado .

La máquina de estados de torniquete se puede representar mediante una tabla de transición de estados , que muestra para cada estado posible las transiciones entre ellos (en función de las entradas proporcionadas a la máquina) y las salidas resultantes de cada entrada:

La máquina de estados del torniquete también puede representarse mediante un grafo dirigido llamado diagrama de estados (arriba) . Cada estado está representado por un nodo ( círculo ). Las aristas ( flechas ) muestran las transiciones de un estado a otro. Cada flecha está etiquetada con la entrada que desencadena dicha transición. Una entrada que no provoca un cambio de estado (como la entrada de una moneda en el estado Desbloqueado ) está representada por una flecha circular que regresa al estado original. La flecha que apunta al nodo Bloqueado desde el punto negro indica que se trata del estado inicial.

Conceptos y terminología

Un estado describe la situación de un sistema que espera ejecutar una transición . Una transición es un conjunto de acciones que se ejecutan cuando se cumple una condición o se recibe un evento. Por ejemplo, al usar un sistema de audio para escuchar la radio (el sistema está en el estado "radio"), recibir el estímulo "siguiente" provoca el cambio a la siguiente emisora. Cuando el sistema está en el estado "CD", el estímulo "siguiente" provoca el cambio a la siguiente pista. Los mismos estímulos desencadenan acciones diferentes según el estado actual.

En algunas representaciones de máquinas de estados finitos, también es posible asociar acciones con un estado:

una acción de entrada: realizada al ingresar al estado, y
una acción de salida: se realiza al salir del estado.

Representaciones

Figura 2. Ejemplo de máquina de estados SDL.

Tabla de estado/evento

Se utilizan varios tipos de tablas de transición de estados . La representación más común se muestra a continuación: la combinación del estado actual (p. ej., B) y la entrada (p. ej., Y) muestra el siguiente estado (p. ej., C). Por sí sola, la tabla no puede describir completamente la acción, por lo que es común usar notas al pie. Otras representaciones relacionadas pueden no tener esta limitación. Por ejemplo, es posible definir una máquina de estados finitos (FSM) que incluya toda la información de la acción utilizando tablas de estados (véase también máquina virtual de estados finitos ).

Máquinas de estados UML

El Lenguaje Unificado de Modelado (UML) cuenta con una notación para describir máquinas de estados. Las máquinas de estados UML superan las limitaciones ^{[ 9 ]} de las máquinas de estados finitos tradicionales, conservando sus principales ventajas. Introducen los nuevos conceptos de estados jerárquicamente anidados y regiones ortogonales , extendiendo la noción de acciones . Las máquinas de estados UML poseen características tanto de las máquinas de Mealy como de las de Moore . Admiten acciones que dependen tanto del estado del sistema como del evento desencadenante , al igual que en las máquinas de Mealy, así como acciones de entrada y salida , asociadas a estados en lugar de transiciones, como en las máquinas de Moore. ^{[ 10 ]}

Máquinas de estado SDL

El lenguaje de especificación y descripción es un estándar de la UIT que incluye símbolos gráficos para describir acciones en la transición:

enviar un evento
recibir un evento
iniciar un temporizador
cancelar un temporizador
iniciar otra máquina de estados concurrente
decisión

SDL incorpora tipos de datos básicos llamados "Tipos de Datos Abstractos", un lenguaje de acción y una semántica de ejecución para hacer que la máquina de estados finitos sea ejecutable. ^{[ 11 ]}

Otros diagramas de estado

Existen numerosas variantes para representar una máquina de estados finitos como la que se muestra en la figura 3.

Uso

Además de su uso en el modelado de sistemas reactivos, como se presenta aquí, las máquinas de estados finitos son importantes en diversas áreas, como la ingeniería eléctrica , la lingüística , la informática , la filosofía , la biología , las matemáticas , la programación de videojuegos y la lógica . Las máquinas de estados finitos son una clase de autómatas estudiados en la teoría de autómatas y la teoría de la computación . En informática, se utilizan ampliamente en el modelado del comportamiento de las aplicaciones ( teoría de control ), el diseño de sistemas digitales de hardware , la ingeniería de software , los compiladores , los protocolos de red y la lingüística computacional .

Clasificación

Las máquinas de estados finitos se pueden subdividir en aceptadores, clasificadores, transductores y secuenciadores. ^{[ 12 ]}

Aceptadores

Fig. 5: Representación de un aceptor; este ejemplo muestra uno que determina si un número binario tiene un número par de 0, donde S ₁ es un *estado de aceptación* y S ₂ es un *estado de no aceptación* .

Los aceptadores (también llamados detectores o reconocedores ) producen una salida binaria que indica si la entrada recibida es aceptada o no. Cada estado de un aceptador es de aceptación o de rechazo . Una vez recibida toda la entrada, si el estado actual es de aceptación, la entrada se acepta; de lo contrario, se rechaza. Por regla general, la entrada es una secuencia de símbolos (caracteres); no se utilizan acciones. El estado inicial también puede ser de aceptación, en cuyo caso el aceptador acepta la cadena vacía. El ejemplo de la figura 4 muestra un aceptador que acepta la cadena "nice". En este aceptador, el único estado de aceptación es el estado 7.

Un conjunto (posiblemente infinito) de secuencias de símbolos, denominado lenguaje formal , es un lenguaje regular si existe algún aceptador que acepte exactamente ese conjunto. ^{[ 13 ]} Por ejemplo, el conjunto de cadenas binarias con un número par de ceros es un lenguaje regular (véase la figura 5), mientras que el conjunto de todas las cadenas cuya longitud es un número primo no lo es. ^{[ 14 ]}

Un aceptador también podría describirse como la definición de un lenguaje que contendría todas las cadenas aceptadas por el aceptador, pero ninguna de las rechazadas; ese lenguaje es aceptado por el aceptador. Por definición, los lenguajes aceptados por los aceptadores son los lenguajes regulares .

El problema de determinar el lenguaje aceptado por un receptor dado es una instancia del problema del camino algebraico, que a su vez es una generalización del problema del camino más corto a grafos con aristas ponderadas por los elementos de un semianillo (arbitrario) . ^{[ 15 ]}^{[ 16 ]}

En la figura 5 se muestra un ejemplo de estado de aceptación: un autómata finito determinista (AFD) que detecta si la cadena binaria de entrada contiene un número par de ceros.

S1 (que también es el estado inicial) indica el estado en el que se ha introducido un número par de ceros. Por lo tanto, S1 _es_un estado de aceptación. Este aceptador finalizará en un estado de aceptación si la cadena binaria contiene un número par de ceros (incluida cualquier cadena binaria que no contenga ceros). Ejemplos de cadenas aceptadas por este aceptador son ε (la cadena vacía ), 1, 11, 11..., 00, 010, 1010, 10110, etc.

Clasificadores

Los clasificadores son una generalización de los aceptadores que producen una salida n -aria donde n es estrictamente mayor que dos. ^{[ 17 ]}

Transductores

Los transductores generan una salida en función de una entrada y/o un estado determinados mediante acciones. Se utilizan en aplicaciones de control y en el campo de la lingüística computacional .

En las aplicaciones de control, se distinguen dos tipos:

Máquina de Moore: La máquina de estados finitos (FSM) utiliza únicamente acciones de entrada, es decir, la salida depende solo del estado. La ventaja del modelo de Moore radica en la simplificación del comportamiento. Consideremos la puerta de un ascensor. La máquina de estados reconoce dos comandos: "comando_abrir" y "comando_cerrar", que desencadenan cambios de estado. La acción de entrada (E:) en el estado "Apertura" inicia un motor que abre la puerta; la acción de entrada en el estado "Cierre" inicia un motor en la dirección opuesta que la cierra. Los estados "Abierta" y "Cerrada" detienen el motor cuando la puerta está completamente abierta o cerrada. Estos estados indican al exterior (por ejemplo, a otras máquinas de estados) la situación: "la puerta está abierta" o "la puerta está cerrada".

Máquina harinosa: La máquina de estados finitos (FSM) también utiliza acciones de entrada, es decir, la salida depende de la entrada y del estado. El uso de una FSM de Mealy suele conllevar una reducción del número de estados. El ejemplo de la figura 7 muestra una FSM de Mealy que implementa el mismo comportamiento que en el ejemplo de Moore (el comportamiento depende del modelo de ejecución de la FSM implementada y funcionará, por ejemplo, para FSM virtuales pero no para FSM controladas por eventos ). Hay dos acciones de entrada (I:): "arrancar el motor para cerrar la puerta si llega el comando_close" y "arrancar el motor en la otra dirección para abrir la puerta si llega el comando_open". Los estados intermedios de "apertura" y "cierre" no se muestran.

Secuenciadores

Los secuenciadores (también llamados generadores ) son una subclase de aceptadores y transductores que tienen un alfabeto de entrada de una sola letra. Producen una única secuencia, que puede considerarse como una secuencia de salida de las salidas del aceptador o transductor. ^{[ 12 ]}

Determinismo

Otra distinción importante es la que existe entre autómatas deterministas ( AFD ) y no deterministas ( AFN , AFGN ). En un autómata determinista, cada estado tiene exactamente una transición para cada entrada posible. En un autómata no determinista, una entrada puede dar lugar a una, varias o ninguna transición para un estado dado. El algoritmo de construcción de conjuntos potencia puede transformar cualquier autómata no determinista en un autómata determinista (generalmente más complejo) con funcionalidad idéntica.

Una máquina de estados finitos con un solo estado se denomina "máquina de estados finitos combinatoria". Solo permite acciones al transitar a un estado. Este concepto resulta útil en casos donde se requiere que varias máquinas de estados finitos trabajen conjuntamente, y cuando es conveniente considerar una parte puramente combinatoria como una forma de máquina de estados finitos que se ajuste a las herramientas de diseño. ^{[ 18 ]}

semántica alternativa

Existen otros conjuntos de semántica disponibles para representar máquinas de estados. Por ejemplo, hay herramientas para modelar y diseñar lógica para controladores embebidos. ^{[ 19 ]} Estas combinan máquinas de estados jerárquicas (que generalmente tienen más de un estado actual), grafos de flujo y tablas de verdad en un solo lenguaje, lo que resulta en un formalismo y un conjunto de semántica diferentes. ^{[ 20 ]} Estos diagramas, como las máquinas de estados originales de Harel , ^{[ 21 ]} admiten estados anidados jerárquicamente, regiones ortogonales , acciones de estado y acciones de transición. ^{[ 22 ]}

Modelo matemático

De acuerdo con la clasificación general, se encuentran las siguientes definiciones formales.

Una máquina de estados finitos determinista o un aceptador de estados finitos determinista es una quíntupla. $(\Sigma ,S,s_{0},\delta ,F)$ , dónde:

$\Sigma$ es el alfabeto de entrada (un conjunto finito no vacío de símbolos);
$S$ es un conjunto finito no vacío de estados;
$s_{0}$ es un estado inicial, un elemento de $S$ ;
$\delta$ es la función de transición de estado: $\delta :S\times \Sigma \rightarrow S$ (en un autómata finito no determinista sería $\delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)$ , es decir $\delta$ devolvería un conjunto de estados);
$F$ es el conjunto de estados finales, un subconjunto (posiblemente vacío) de $S$ .

Para las máquinas de estados finitos deterministas y no deterministas, es convencional permitir $\delta$ ser una función parcial , es decir $\delta (s,x)$ no tiene que definirse para cada combinación de $s\in S$ y $x\in \Sigma$ Si una máquina de estados finitos (FSM) $M$ está en un estado $s$ , el siguiente símbolo es $x$ y $\delta (s,x)$ no está definido, entonces $M$ Puede anunciar un error (es decir, rechazar la entrada). Esto es útil en las definiciones de máquinas de estados generales, pero menos útil al transformar la máquina. Algunos algoritmos en su forma predeterminada pueden requerir funciones totales.

Una máquina de estados finitos tiene la misma capacidad computacional que una máquina de Turing restringida, cuyo cabezal solo puede realizar operaciones de "lectura" y siempre debe moverse de izquierda a derecha. Es decir, cada lenguaje formal aceptado por una máquina de estados finitos es aceptado por este tipo de máquina de Turing restringida, y viceversa. ^{[ 23 ]}

Un transductor de estado finito es un séxtuple $(\Sigma,\Gamma,S,s_{0},\delta,\omega)$ , dónde:

$\Sigma$ es el alfabeto de entrada (un conjunto finito no vacío de símbolos);
$\Gamma$ es el alfabeto de salida (un conjunto finito no vacío de símbolos);
$S$ es un conjunto finito no vacío de estados;
$s_{0}$ es el estado inicial, un elemento de $S$ ;
$\delta$ es la función de transición de estado: $\delta :S\times \Sigma \rightarrow S$ ;
$\omega$ es la función de salida.

Si la función de salida depende del estado y del símbolo de entrada ( $\omega :S\times \Sigma \rightarrow \Gamma$ ) esa definición corresponde al modelo de Mealy y puede modelarse como una máquina de Mealy . Si la función de salida depende únicamente del estado ( $\omega :S\rightarrow \Gamma$ ) esa definición corresponde al modelo de Moore y puede modelarse como una máquina de Moore . Una máquina de estados finitos sin ninguna función de salida se conoce como semiautómata o sistema de transición .

Si ignoramos el primer símbolo de salida de una máquina de Moore, $\omega (s_ {0})$ Entonces, se puede convertir fácilmente en una máquina de Mealy equivalente en salida estableciendo la función de salida de cada transición de Mealy (es decir, etiquetando cada arista) con el símbolo de salida dado del estado de Moore de destino. La transformación inversa es menos directa porque un estado de máquina de Mealy puede tener diferentes etiquetas de salida en sus transiciones (aristas) de entrada. Cada uno de esos estados debe dividirse en múltiples estados de máquina de Moore, uno para cada símbolo de salida incidente. ^{[ 24 ]}

Mejoramiento

Optimizar una máquina de estados finitos (FSM) significa encontrar una máquina con el número mínimo de estados que realice la misma función. El algoritmo más rápido conocido para esto es el algoritmo de minimización de Hopcroft . ^{[ 25 ]}^{[ 26 ]} Otras técnicas incluyen el uso de una tabla de implicación o el procedimiento de reducción de Moore. ^{[ 27 ]} Además, los autómatas de estados finitos acíclicos se pueden minimizar en tiempo lineal . ^{[ 28 ]}

Implementación

Aplicaciones de hardware

En un circuito digital , una máquina de estados finitos (FSM) puede construirse utilizando un dispositivo lógico programable (PLC ) , un controlador lógico programable (PLC) , puertas lógicas y biestables o relés . Más específicamente, una implementación de hardware requiere un registro para almacenar variables de estado, un bloque de lógica combinacional que determina la transición de estado y un segundo bloque de lógica combinacional que determina la salida de la FSM.

En una máquina de Medvedev , la salida está conectada directamente a los flip-flops de estado, minimizando el retardo de tiempo entre los flip-flops y la salida. ^{[ 29 ]}^{[ 30 ]}

Mediante la codificación de estados, las máquinas de estados de bajo consumo pueden optimizarse para minimizar el consumo de energía.

Aplicaciones de software

Los siguientes conceptos se utilizan comúnmente para construir aplicaciones de software con máquinas de estados finitos:

Máquinas de estados finitos y compiladores

Los autómatas finitos se utilizan frecuentemente en la interfaz de los compiladores de lenguajes de programación. Dicha interfaz puede constar de varias máquinas de estados finitos que implementan un analizador léxico y un analizador sintáctico. Partiendo de una secuencia de caracteres, el analizador léxico construye una secuencia de tokens del lenguaje (como palabras reservadas, literales e identificadores) a partir de la cual el analizador sintáctico construye un árbol sintáctico. El analizador léxico y el analizador sintáctico gestionan las partes regulares y libres de contexto de la gramática del lenguaje de programación. ^{[ 31 ]}

Referencias

↑ Minsky (1967) introduce los términos alternativos, máquinas de estados finitos y autómatas finitos , al comienzo del Capítulo 2 .
↑ Wang 2019 , pág. 34.
↑ Brillante .
↑ Lewis & Papadimitriou 1998 , Capítulo 2: Autómatas finitos .
^ Lewis y Papadimitriou 1998 , pág. 64 .
↑ Belzer, Holzman y Kent 1975 , pág. 73.
1 2 Koshy 2004 .
↑ Wright 2005 .
↑ Börger, Egon; Cavarra, Alessandra; Riccobene, Elvinia (2000). Gurevich, Yuri; Kutter, Philipp W.; Odersky, Martin; Thiele, Lothar (eds.). "Modelado de la dinámica de las máquinas de estados UML" . Máquinas de estados abstractas: teoría y aplicaciones . Berlín, Heidelberg: Springer: 223–241 . doi : 10.1007/3-540-44518-8_13 . ISBN 978-3-540-44518-0.
↑ "Un curso intensivo sobre máquinas de estados UML" (PDF) . Quantum Leaps, LLC . Consultado el 13 de junio de 2026 .
↑ "La semántica formal de SDL-2000: estado y perspectivas" . Computer Networks . 42 (3): 343–358 . 21 de junio de 2003. doi : 10.1016/S1389-1286(03)00247-0 . ISSN 1389-1286 .
1 2 Keller 2001 .
↑ Hopcroft y Ullman 1979 , págs. 18.
↑ Hopcroft, Motwani y Ullman 2006 , págs. 130–131.
↑ Pouly y Kohlas 2011 , pág. 223, Capítulo 6. Álgebras de valuación para problemas de caminos.
↑ Jonczy 2008 , pág. 34.
↑ Felkin 2007 , págs. 277–278.
↑ Brutscheck et al. 2008 .
↑ Tiwari 2002 .
↑ Hamon 2005 .
↑ Harel 1987 .
↑ Alur et al. 2008 .
↑ Negro 2008 .
↑ Anderson y Head 2006 , págs. 105–108.
↑ Hopcroft 1971 .
↑ Almeida, Moreira & Reis 2007 .
↑ Moore 1956 , pág. 142, Teorema 4.
↑ Revuz 1992 .
↑ Kaeslin 2008 .
↑ Schwarz .
^ Aho, Sethi y Ullman 1986 .

Fuentes

Aho, Alfred V.; Sethi , Ravi ; Ullman, Jeffrey D. (1986). Compiladores: Principios, técnicas y herramientas (1.ª ed.). Addison-Wesley . ISBN 978-0-201-10088-4.
Almeida, Marco; Moreira, Nelma; Reis, Rogerio (2007). Sobre el rendimiento de algoritmos de minimización de autómatas (PDF) (Informe técnico). vol. DCC-2007-03. Universidad de Oporto. Archivado desde el original (PDF) el 17 de enero de 2009 . Consultado el 25 de junio de 2008 .
Alur, R.; Kanade, A.; Ramesh, S.; Shashidhar, KC (2008). "Análisis simbólico para mejorar la cobertura de simulación de modelos Simulink/Stateflow. Conferencia Internacional sobre Software Embebido (págs. 89–98). Atlanta, GA: ACM" (PDF) . Archivado del original (PDF) el 15 de julio de 2011.
Anderson, James Andrew; Head, Thomas J. (2006). Teoría de autómatas con aplicaciones modernas . Cambridge University Press. ISBN 978-0-521-84887-9.
Belzer, Jack; Holzman, Albert George; Kent, Allen (1975). Enciclopedia de Ciencias de la Computación y Tecnología . Vol. 25. EE. UU.: CRC Press. ISBN 978-0-8247-2275-3.
Black, Paul E (12 de mayo de 2008). "Máquina de estados finitos" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de EE. UU . Archivado del original el 13 de octubre de 2018. Recuperado el 2 de noviembre de 2016 .
"Máquinas de estados finitos – Wiki brillante de matemáticas y ciencias" . brilliant.org . Consultado el 14 de abril de 2018 .
Brutscheck, M.; Berger, S.; Franke, M.; Schwarzbacher, A.; Becker, S. (2008). Actas de la Conferencia Irlandesa de Señales y Sistemas del IET (ISSC 2008), 18-19 de junio de 2008. Procedimiento de división estructural para un análisis eficiente de circuitos integrados. Galway, Irlanda. págs. 18-23 .
Felkin, M. (2007). «Comparación de resultados de clasificación entre problemas N-arios y binarios». En Guillet, Fabrice; Hamilton, Howard J. (eds.). Medidas de calidad en minería de datos: estudios en inteligencia computacional . Vol. 43. Springer, Berlín, Heidelberg. pp. 277–301 . doi : 10.1007/978-3-540-44918-8_12 . ISBN 978-3-540-44911-9.
Hamon, G. (2005). Una semántica denotacional para Stateflow . Conferencia internacional sobre software embebido. Jersey City, NJ: ACM. pp. 164–172 . CiteSeerX 10.1.1.89.8817 .
Harel, D. (1987). "Un formalismo visual para sistemas complejos. Science of Computer Programming, 231–274" (PDF) . Archivado del original (PDF) el 15 de julio de 2011. Recuperado el 7 de junio de 2011 .
Hopcroft, John (1971). «Un algoritmo n log n para minimizar estados en un autómata finito» . Theory of Machines and Computations . Elsevier: 189–196 . doi : 10.1016/b978-0-12-417750-5.50022-1 . ISBN 978-0-12-417750-5Consultado el 18 de septiembre de 2025 .
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley. ISBN 0-201-02988-X.( Accesible para usuarios con discapacidades visuales )
Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2006) [1979]. Introducción a la teoría de autómatas, lenguajes y computación (3.ª ed.). Addison-Wesley. ISBN 0-321-45536-3.
Jonczy, Jacek (junio de 2008). "Problemas de caminos algebraicos" (PDF) . Archivado del original (PDF) el 21 de agosto de 2014. Recuperado el 20 de agosto de 2014 .
Kaeslin, Hubert (2008). «Mealy, Moore, Medvedev-type and combinatorial output bits» . Diseño de circuitos integrados digitales: De las arquitecturas VLSI a la fabricación CMOS . Cambridge University Press. p. 787. ISBN 978-0-521-88267-5.
Keller, Robert M. (2001). "Clasificadores, aceptadores, transductores y secuenciadores" (PDF) . Ciencias de la Computación: De la abstracción a la implementación (PDF) . Harvey Mudd College. pág. 480.
Koshy, Thomas (2004). Matemáticas discretas con aplicaciones . Academic Press. pág. 762. ISBN 978-0-12-421180-3.
Moore, Edward F. (1956). CE Shannon y J. McCarthy (eds.). "Gedanken-Experiments on Sequential Machines". Annals of Mathematics Studies . 34. Princeton University Press: 129–153 .
Pouly, Marc; Kohlas, Jürg (2011). Inferencia genérica: una teoría unificadora para el razonamiento automatizado . John Wiley & Sons. ISBN 978-1-118-01086-0.
Revuz, D. (1992). "Minimización de autómatas acíclicos en tiempo lineal". Theoretical Computer Science . 92 : 181–189 . doi : 10.1016/0304-3975(92)90142-3 .
Schwarz, B. «Máquinas síncronas de estados finitos: diseño y comportamiento» (PDF) . Universidad de Ciencias Aplicadas de Hamburgo . pág. 18. Archivado del original (PDF) el 18 de enero de 2017. Consultado el 16 de abril de 2026 .
Tiwari, A. (2002). "Métodos de análisis y semántica formal para modelos Stateflow de Simulink" (PDF) . sri.com . Recuperado el 14 de abril de 2018 .
Wang, Jiacun (2019). Métodos formales en informática . CRC Press. ISBN 978-1-4987-7532-8.
Wright, David R. (2005). "Máquinas de estados finitos" (PDF) . Apuntes de clase de CSC215 . Sitio web de David R. Wright, Universidad Estatal de Carolina del Norte. Archivado del original (PDF) el 27 de marzo de 2014. Recuperado el 14 de julio de 2012 .

Lecturas adicionales

General

Carroll, J.; Long, D. (1989). Teoría de autómatas finitos con una introducción a los lenguajes formales (PDF) . Englewood Cliffs: Prentice Hall.
Cassandras, C.; Lafortune, S. (1999). Introducción a los sistemas de eventos discretos . Kluwer. ISBN 0-7923-8609-4.
Gardner, T. (2007). "Advanced State Management" . Archivado del original el 19 de noviembre de 2008.
Gill, A. (1962). Introducción a la teoría de las máquinas de estados finitos . McGraw-Hill.
Ginsburg, S. (1962). Una introducción a la teoría matemática de máquinas . Addison-Wesley.
UIT-T. "Recomendación Z.100 Lenguaje de especificación y descripción (SDL)" .
Kam, Timothy (1997). Síntesis de máquinas de estados finitos: optimización funcional . Boston: Kluwer Academic Publishers. ISBN 0-7923-9842-4.
Kohavi, Z. (1978). Conmutación y teoría de autómatas finitos . McGraw-Hill.
Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177 .
Samek, M. (2002). Diagramas de estados prácticos en C/C++ . CMP Books. ISBN 1-57820-110-1.
Samek, M. (2008). Diagramas de estados UML prácticos en C/C++, 2.ª edición . Newnes. ISBN 0-7506-8706-1.
Villa, Tiziano (1997). Síntesis de máquinas de estados finitos: optimización lógica . Boston: Kluwer Academic Publishers. ISBN 0-7923-9892-0.
Wagner, F. (2006). Modelado de software con máquinas de estados finitos: un enfoque práctico . Auerbach Publications. ISBN 0-8493-8086-3.

Máquinas de estados finitos (teoría de autómatas) en informática teórica

Arbib, Michael A. (1969). Teorías de los autómatas abstractos (1.ª ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
Bobrow, Leonard S.; Arbib, Michael A. (1974). Matemáticas discretas: Álgebra aplicada a la informática y las ciencias de la información (1.ª ed.). Filadelfia: WB Saunders Company, Inc. ISBN 978-0-7216-1768-8.
Booth, Taylor L. (1967). Máquinas secuenciales y teoría de autómatas (1.ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de la Biblioteca del Congreso: 67-25924.
Boolos, George; Jeffrey, Richard (1999) [1989]. Computabilidad y lógica (3.ª ed.). Cambridge, Inglaterra: Cambridge University Press. ISBN 978-0-521-20402-6.
Brookshear, J. Glenn (1989). Teoría de la computación: lenguajes formales, autómatas y complejidad . Redwood City, California: Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidad, complejidad y lenguajes y lógica: Fundamentos de la informática teórica (2.ª ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 978-0-12-206382-4.
Hopkins, David; Moss, Bárbara (1976). Autómatas . Nueva York: Elsevier Holanda Septentrional. ISBN 978-0-444-00249-5.
Kozen, Dexter C. (1997). Autómatas y computabilidad (1ª ed.). Nueva York: Springer-Verlag. ISBN 978-0-387-94907-9.
Lewis, Harry R.; Papadimitriou , Christos H. (1998). Elementos de la teoría de la computación (2.ª ed.). Upper Saddle River, Nueva Jersey: Prentice-Hall. ISBN 978-0-13-262478-7.
Linz, Peter (2006). Lenguajes formales y autómatas (4.ª ed.). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3798-6.
Minsky, Marvin (1967). Computación: Máquinas finitas e infinitas (1.ª ed.). Nueva Jersey: Prentice-Hall.
Papadimitriou, Christos (1993). Complejidad computacional (1.ª ed.). Addison Wesley. ISBN 978-0-201-53082-7.
Pippenger, Nicholas (1997). Teorías de la computabilidad (1.ª ed.). Cambridge, Inglaterra: Cambridge University Press. ISBN 978-0-521-55380-3.
Rodger, Susan; Finley, Thomas (2006). JFLAP: Un paquete interactivo de lenguajes formales y autómatas (1.ª ed.). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3834-1.
Sipser, Michael (2006). Introducción a la teoría de la computación (2.ª ed.). Boston, Massachusetts: Thomson Course Technology. ISBN 978-0-534-95097-2.
Wood, Derick (1987). Teoría de la computación (1.ª ed.). Nueva York: Harper & Row, Publishers, Inc. ISBN 978-0-06-047208-5.

Máquinas de estados abstractas en informática teórica

Gurevich, Yuri (julio de 2000). "Máquinas de estados abstractos secuenciales capturan algoritmos secuenciales" (PDF) . ACM Transactions on Computational Logic . 1 (1): 77– 111. CiteSeerX 10.1.1.146.3017 . doi : 10.1145/343369.343384 . S2CID 2031696 .

Aprendizaje automático mediante algoritmos de estados finitos

Mitchell, Tom M. (1997). Aprendizaje automático (1.ª ed.). Nueva York: WCB/McGraw-Hill Corporation. ISBN 978-0-07-042807-2.

Ingeniería de hardware: Minimización de estados y síntesis de circuitos secuenciales

Booth, Taylor L. (1967). Máquinas secuenciales y teoría de autómatas (1.ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de la Biblioteca del Congreso: 67-25924.
Booth, Taylor L. (1971). Redes digitales y sistemas informáticos (1.ª ed.). Nueva York: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
McCluskey, EJ (1965). Introducción a la teoría de los circuitos de conmutación (1.ª ed.). Nueva York: McGraw-Hill Book Company, Inc. Número de catálogo de la Biblioteca del Congreso: 65-17394.
Hill, Fredrick J.; Peterson, Gerald R. (1965). Introducción a la teoría de los circuitos de conmutación (1.ª ed.). Nueva York: McGraw-Hill Book Company. Número de catálogo de la Biblioteca del Congreso: 65-17394.

Procesos de cadena de Markov finita

Podemos pensar en una cadena de Markov como un proceso que se mueve sucesivamente a través de un conjunto de estados s ₁ , s ₂ , …, s _r . … si se encuentra en el estado s _i , pasa a la siguiente parada al estado s _j con probabilidad p _ij . Estas probabilidades se pueden representar en forma de una matriz de transición.

— Kemeny et al. 1959 , pág. 384

Los procesos de cadena de Markov finita también se conocen como subdesplazamientos de tipo finito .

Booth, Taylor L. (1967). Máquinas secuenciales y teoría de autómatas (1.ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de la Biblioteca del Congreso: 67-25924.
Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Estructuras matemáticas finitas (1.ª ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc. Número de catálogo de la Biblioteca del Congreso: 59-12841.Capítulo 6 "Cadenas de Markov finitas".

Enlaces externos

"La guía completa de las máquinas de estados" . statecharts.online .– Tutorial completo e interactivo sobre diagramas de estados y máquinas de estados

GetLastError. "Modelado de un comportamiento de IA simple mediante una máquina de estados finitos" . Blog de desarrollo de juegos de Manuvra . Archivado del original el 2 de diciembre de 2012.

"Máquina de estados finitos" . Diccionario en línea gratuito de informática . Archivado del original el 11 de diciembre de 2017.– Descripción de las máquinas de estados finitos

"Máquina de estados finitos" . Diccionario de algoritmos y estructuras de datos del NIST. Archivado del original el 13 de octubre de 2018.– Descripción de las máquinas de estados finitos

"A brief overview of state machine types". itemis Blog. itemis AG. – Comparing theoretical aspects of Mealy, Moore, Harel & UML state machines

[1] Minsky (1967) introduce los términos alternativos, máquinas de estados finitos y autómatas finitos , al comienzo del Capítulo 2 .

[FOOTNOTEWang201934-2] Wang 2019 , pág. 34.

[FOOTNOTEBrilliant-3] Brillante .

[FOOTNOTELewisPapadimitriou1998[httpsarchiveorgdetailselementsoftheory0000lewi_n0x1pagen10mode1upq222finiteautomata22_Chapter_2:_Finite_Automata]-4] Lewis & Papadimitriou 1998 , Capítulo 2: Autómatas finitos .

[FOOTNOTELewisPapadimitriou1998[httpsarchiveorgdetailselementsoftheory0000lewi_n0x1page64mode2upqequivalent_64]-5] Lewis y Papadimitriou 1998 , pág. 64 .

[FOOTNOTEBelzerHolzmanKent197573-6] Belzer, Holzman y Kent 1975 , pág. 73.

[FOOTNOTEKoshy2004-7] 1 2 Koshy 2004 .

[FOOTNOTEWright2005-8] Wright 2005 .

[9] Börger, Egon; Cavarra, Alessandra; Riccobene, Elvinia (2000). Gurevich, Yuri; Kutter, Philipp W.; Odersky, Martin; Thiele, Lothar (eds.). "Modelado de la dinámica de las máquinas de estados UML" . Máquinas de estados abstractas: teoría y aplicaciones . Berlín, Heidelberg: Springer: 223–241 . doi : 10.1007/3-540-44518-8_13 . ISBN 978-3-540-44518-0.

[10] "Un curso intensivo sobre máquinas de estados UML" (PDF) . Quantum Leaps, LLC . Consultado el 13 de junio de 2026 .

[11] "La semántica formal de SDL-2000: estado y perspectivas" . Computer Networks . 42 (3): 343–358 . 21 de junio de 2003. doi : 10.1016/S1389-1286(03)00247-0 . ISSN 1389-1286 .

[FOOTNOTEKeller2001-12] 1 2 Keller 2001 .

[FOOTNOTEHopcroftUllman197918-13] Hopcroft y Ullman 1979 , págs. 18.

[FOOTNOTEHopcroftMotwaniUllman2006130–131-14] Hopcroft, Motwani y Ullman 2006 , págs. 130–131.

[FOOTNOTEPoulyKohlas2011223Chapter_6._Valuation_Algebras_for_Path_Problems-15] Pouly y Kohlas 2011 , pág. 223, Capítulo 6. Álgebras de valuación para problemas de caminos.

[FOOTNOTEJonczy200834-16] Jonczy 2008 , pág. 34.

[FOOTNOTEFelkin2007277–278-17] Felkin 2007 , págs. 277–278.

[FOOTNOTEBrutscheckBergerFrankeSchwarzbacher2008-18] Brutscheck et al. 2008 .

[FOOTNOTETiwari2002-19] Tiwari 2002 .

[FOOTNOTEHamon2005-20] Hamon 2005 .

[FOOTNOTEHarel1987-21] Harel 1987 .

[FOOTNOTEAlurKanadeRameshShashidhar2008-22] Alur et al. 2008 .

[FOOTNOTEBlack2008-23] Negro 2008 .

[FOOTNOTEAndersonHead2006105–108-24] Anderson y Head 2006 , págs. 105–108.

[FOOTNOTEHopcroft1971-25] Hopcroft 1971 .

[FOOTNOTEAlmeidaMoreiraReis2007-26] Almeida, Moreira & Reis 2007 .

[FOOTNOTEMoore1956142Theorem_4-27] Moore 1956 , pág. 142, Teorema 4.

[FOOTNOTERevuz1992-28] Revuz 1992 .

[FOOTNOTEKaeslin2008-29] Kaeslin 2008 .

[FOOTNOTESchwarz-30] Schwarz .

[FOOTNOTEAhoSethiUllman1986-31] Aho, Sethi y Ullman 1986 .

[

[

[

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]