Máquina de estados finitos

Modelo matemático de computación.

clases de autómatas

Una máquina de estados finitos ( FSM ) o autómata de estados finitos ( FSA , plural: autómatas ), autómata finito , o simplemente una máquina de estados , 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] Un FSM se define por 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 de estados finitos no deterministas . ^[2] Para cualquier máquina de estados finitos no determinista, se puede construir una determinista equivalente.

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 dependiendo 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 adecuada de monedas; ascensores , cuya secuencia de paradas está determinada por los pisos solicitados por los usuarios; semáforos , que cambian de secuencia cuando hay coches esperando; 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 realizar pero que un FSM no. Esto se debe a que la memoria de un FSM está limitada por la cantidad de estados que tiene. Una máquina de estados finitos tiene la misma potencia computacional que una máquina de Turing, pero está restringida de modo 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 los autómatas .

Ejemplo: torniquete que funciona con monedas

Diagrama de estado de un torniquete.

un torniquete

Un ejemplo de mecanismo simple que puede ser modelado por una máquina de estados es un torniquete . ^{[4] [5]} 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 cruzando 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 pueda pasar. Una vez 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 posibles entradas que afectan a su estado: meter una moneda en la ranura para monedas y empujar el brazo de empuje . En el estado bloqueado, empujar el brazo no tiene ningún efecto; no importa cuántas veces se presione la entrada , permanece en el estado bloqueado. Al introducir una moneda, es decir, darle a la máquina una entrada de moneda , el estado cambia de Bloqueado a Desbloqueado . En el estado desbloqueado, poner monedas adicionales no tiene ningún efecto; es decir, dar entradas adicionales de monedas no cambia el estado. Un cliente que empuja a través de los brazos da un impulso y restablece el estado a Bloqueado .

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

La máquina de estados del torniquete también se puede representar mediante un gráfico dirigido llamado diagrama de estado (arriba) . Cada estado está representado por un nodo ( círculo ). Los bordes ( flechas ) muestran las transiciones de un estado a otro. Cada flecha está etiquetada con la entrada que desencadena esa transición. Una entrada que no provoca un cambio de estado (como una entrada de moneda en el estado Desbloqueado ) se representa mediante una flecha circular que regresa al estado original. La flecha hacia el nodo Bloqueado desde el punto negro indica que es el estado inicial.

Conceptos y terminología

Un estado es una descripción del estado de un sistema que está esperando ejecutar una transición . Una transición es un conjunto de acciones que se ejecutarán cuando se cumpla una condición o cuando se reciba un evento. Por ejemplo, cuando se utiliza un sistema de audio para escuchar la radio (el sistema está en el estado de "radio"), recibir un "siguiente" estímulo da como resultado pasar a la siguiente estación. Cuando el sistema está en el estado "CD", el "siguiente" estímulo da como resultado el paso a la siguiente pista. Estímulos idénticos desencadenan diferentes acciones 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: realizada al salir del estado.

Representaciones

Fig.1 Ejemplo de gráfico de estado UML (un horno tostador)

Fig. 2 Ejemplo de máquina de estados SDL

Fig. 3 Ejemplo de una máquina de estados finitos simple

Tabla de estado/evento

Se utilizan varios tipos de tablas de transición de estado . La representación más común se muestra a continuación: la combinación del estado actual (por ejemplo, B) y la entrada (por ejemplo, Y) muestra el siguiente estado (por ejemplo, C). La información completa de la acción no se describe directamente en la tabla y solo se puede agregar mediante notas a pie de página. ^{[ Se necesita más explicación ]} Es posible obtener una definición de FSM que incluya la información completa de la acción utilizando tablas de estado (consulte también máquina virtual de estados finitos ).

máquinas de estados UML

El Lenguaje Unificado de Modelado tiene una notación para describir máquinas de estados. Las máquinas de estados UML superan las limitaciones ^{[ cita necesaria ]} de las máquinas de estados finitos tradicionales conservando sus principales beneficios. Las máquinas de estados UML introducen los nuevos conceptos de estados jerárquicamente anidados y regiones ortogonales , al tiempo que amplían la noción de acciones . Las máquinas de estados UML tienen las características tanto de las máquinas Mealy como de las máquinas Moore . Apoyan acciones que dependen tanto del estado del sistema como del evento desencadenante , como en las máquinas de Mealy, así como acciones de entrada y salida , que están asociadas con estados en lugar de transiciones, como en las máquinas de Moore. ^{[ cita necesaria ]}

máquinas de estados 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 concurrentes
• 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 que la máquina de estados finitos sea ejecutable. ^{[ cita necesaria ]}

Otros diagramas de estado

Existe una gran cantidad de variantes para representar un FSM como el de la figura 3.

Uso

Además de su uso en el modelado de sistemas reactivos presentados aquí, las máquinas de estados finitos son importantes en muchas áreas diferentes, incluidas 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 los autómatas y la teoría de la computación . En informática, las máquinas de estados finitos se utilizan ampliamente en el modelado del comportamiento de aplicaciones ( teoría de control ), diseño de sistemas digitales de hardware , ingeniería de software , compiladores , protocolos de red y lingüística computacional .

Clasificación

Las máquinas de estados finitos se pueden subdividir en aceptores, clasificadores, transductores y secuenciadores. ^[6]

Aceptadores

Fig. 4: Aceptador FSM: analizando la cadena "nice".

Fig. 5: Representación de un aceptor; Este ejemplo muestra uno que determina si un número binario tiene un número par de ceros, 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 se acepta o no la entrada recibida. Cada estado de un aceptador es de aceptación o de no aceptación . Una vez que se han recibido todas las entradas, si el estado actual es un estado de aceptación, se acepta la entrada; en caso contrario se rechaza. Como regla general, la entrada es una secuencia de símbolos (caracteres); Las acciones no se utilizan. El estado inicial también puede ser un estado 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, llamado lenguaje formal , es un lenguaje regular si hay algún aceptor que acepte exactamente ese conjunto. Por ejemplo, el conjunto de cadenas binarias con un número par de ceros es un lenguaje regular (cf. Fig. 5), mientras que el conjunto de todas las cadenas cuya longitud es un número primo no lo es. ^{[7] : 18, 71}

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 idioma es aceptado por el aceptante. Por definición, los idiomas aceptados por los aceptantes son los idiomas regulares .

El problema de determinar el lenguaje aceptado por un aceptor dado es un ejemplo del problema de la ruta algebraica , que en sí mismo es una generalización del problema de la ruta más corta a gráficos con aristas ponderadas por los elementos de un semirreno (arbitrario) . ^{[8] [9] [ jerga ]}

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

S ₁ (que también es el estado inicial) indica el estado en el que se ha introducido un número par de ceros. Por tanto, S ₁ 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 aceptores que producen una salida n -aria donde n es estrictamente mayor que dos. ^[10]

Transductores

Fig. 6 Transductor FSM: ejemplo del modelo de Moore

Fig. 7 Transductor FSM: ejemplo del modelo Mealy

Los transductores producen una salida basada en una entrada determinada y/o un estado mediante acciones. Se utilizan para aplicaciones de control y en el campo de la lingüística computacional .

En aplicaciones de control se distinguen dos tipos:

maquina moore

El FSM utiliza sólo acciones de entrada, es decir, la salida depende sólo del estado. La ventaja del modelo de Moore es una simplificación del comportamiento. Considere la puerta de un ascensor. La máquina de estados reconoce dos comandos: "command_open" y "command_close", 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 otra dirección que cierra la puerta. Los estados "Abierto" y "Cerrado" detienen el motor cuando está completamente abierto o cerrado. Señalan al mundo exterior (por ejemplo, a otras máquinas de estados) la situación: "la puerta está abierta" o "la puerta está cerrada".

maquina harinosa

El FSM también utiliza acciones de entrada, es decir, la salida depende de la entrada y el estado. El uso de un FSM harinoso conduce a menudo a una reducción del número de estados. El ejemplo de la figura 7 muestra un FSM de Mealy que implementa el mismo comportamiento que en el ejemplo de Moore (el comportamiento depende del modelo de ejecución de FSM implementado y funcionará, por ejemplo, para FSM virtual pero no para FSM controlado por eventos ). Hay dos acciones de entrada (I:): "arrancar el motor para cerrar la puerta si llega comando_cerrar" y "arrancar el motor en la otra dirección para abrir la puerta si llega comando_abrir". No se muestran los estados intermedios de "apertura" y "cierre".

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 solo una secuencia, que puede verse como una secuencia de salida de salidas de aceptor o transductor. ^[6]

Determinismo

Otra distinción es entre autómatas deterministas ( DFA ) y no deterministas ( NFA , GNFA ). 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 conducir a una, más de una o ninguna transición para un estado determinado. El algoritmo de construcción powerset 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 "FSM combinatoria". Solo permite acciones tras la transición a un estado. Este concepto es útil en los casos en los que se requiere que varias máquinas de estados finitos trabajen juntas y cuando es conveniente considerar una pieza puramente combinatoria como una forma de FSM que se adapte a las herramientas de diseño. ^[11]

Semántica alternativa

Hay otros conjuntos de semántica disponibles para representar máquinas de estados. Por ejemplo, existen herramientas para modelar y diseñar lógica para controladores integrados. ^[12] Combinan máquinas de estados jerárquicos (que generalmente tienen más de un estado actual), gráficos de flujo y tablas de verdad en un solo lenguaje, lo que da como resultado un formalismo y un conjunto de semánticas diferentes. ^[13] Estos gráficos, al igual que las máquinas de estados originales de Harel , ^[14] admiten estados jerárquicamente anidados, regiones ortogonales , acciones de estado y acciones de transición. ^[15]

Modelo matemático

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

Una máquina determinista de estados finitos o un aceptor determinista de estados finitos es un quíntuple , donde: ${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$

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

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

Una máquina de estados finitos tiene la misma potencia computacional que una máquina de Turing , pero está restringida de modo que su cabeza sólo puede realizar operaciones de "lectura" y siempre tiene que moverse de izquierda a derecha. Es decir, cada lenguaje formal aceptado por una máquina de estados finitos es aceptado por un tipo de máquina de Turing restringida, y viceversa. ^[dieciséis]

Un transductor de estados finitos es un séxtuple , donde: ${\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}$

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

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

Si ignoramos el primer símbolo de salida de una máquina de Moore, entonces se puede convertir fácilmente en una máquina de Mealy con salida equivalente configurando la función de salida de cada transición de Mealy (es decir, etiquetando cada borde) con el símbolo de salida dado del destino de Moore. estado. La transformación inversa es menos sencilla porque el estado de una máquina Mealy puede tener diferentes etiquetas de salida en sus transiciones entrantes (bordes). Cada uno de estos estados debe dividirse en múltiples estados de la máquina de Moore, uno para cada símbolo de salida incidente. ^[17] ${\displaystyle \omega (s_{0})}$

Mejoramiento

Optimizar un FSM significa encontrar una máquina con el mínimo número de estados que realice la misma función. El algoritmo conocido más rápido que hace esto es el algoritmo de minimización de Hopcroft . ^{[18] [19]} Otras técnicas incluyen el uso de una tabla de implicaciones o el procedimiento de reducción de Moore. ^[20] Además, las FSA acíclicas se pueden minimizar en el tiempo lineal . ^[21]

Implementación

Aplicaciones de hardware

Fig. 9 El diagrama de circuito de un contador TTL de 4 bits , un tipo de máquina de estados.

En un circuito digital , se puede construir un FSM utilizando un dispositivo lógico programable , un controlador lógico programable , puertas lógicas y flip-flops 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 un FSM. Una de las implementaciones de hardware clásicas es el controlador Richards .

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

A través de la codificación de estado para máquinas de estado de bajo consumo se puede optimizar para minimizar el consumo de energía.

Aplicaciones de software

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

• Programación basada en autómatas
• Máquina de estados finitos impulsada por eventos
• Máquina virtual de estados finitos
• Patrón de diseño estatal

Máquinas de estados finitos y compiladores.

Los autómatas finitos se utilizan a menudo en la interfaz de los compiladores de lenguajes de programación. Una interfaz de este tipo puede comprender varias máquinas de estados finitos que implementan un analizador léxico y un analizador sintáctico. A partir de una secuencia de caracteres, el analizador léxico construye una secuencia de tokens de lenguaje (como palabras reservadas, literales e identificadores) a partir de la cual el analizador construye un árbol de sintaxis. El analizador léxico y el analizador manejan las partes regulares y libres de contexto de la gramática del lenguaje de programación. ^[24]

Ver también

• Máquinas de estados abstractos
• Autómata finito alterno
• Máquina de estados finitos comunicante
• Sistema de control
• mesa de control
• Tablas de decisiones
• DESARROLLADORES
• Modelo de Markov oculto
• Red de Petri
• autómata de empuje
• Autómata cuántico finito
• SCXML
• semiautómata
• Acción de semigrupo
• Lógica secuencial
• Diagrama de estado
• Palabra de sincronización
• Semigrupo de transformación
• Sistema de transición
• autómata de árbol
• máquina de Turing
• máquina de estados UML

Referencias

1. Wang, Jiacun (2019). Métodos formales en informática . Prensa CRC. pag. 34.ISBN _ 978-1-4987-7532-8.
2. "Máquinas de estados finitos - Wiki brillante de matemáticas y ciencias". brillante.org . Consultado el 14 de abril de 2018 .
3. Belzer, Jack; Holzman, Albert George; Kent, Allen (1975). Enciclopedia de informática y tecnología. vol. 25. Estados Unidos: CRC Press. pag. 73.ISBN _ 978-0-8247-2275-3.
4. Koshy, Thomas (2004). Matemáticas discretas con aplicaciones. Prensa académica. pag. 762.ISBN _ 978-0-12-421180-3.
5. Wright, David R. (2005). "Máquinas de estados finitos" (PDF) . Notas de clase CSC215 . Sitio web de David R. Wright, Universidad Estatal de Carolina del Norte. Archivado desde el original (PDF) el 27 de marzo de 2014 . Consultado el 14 de julio de 2012 .
6. Keller, Robert M. (2001). "Clasificadores, Aceptadores, Transductores y Secuenciadores" (PDF) . Ciencias de la Computación: de la abstracción a la implementación (PDF) . Universidad Harvey Mudd. pag. 480.
7. John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de autómatas. Lectura/MA: Addison-Wesley. ISBN 978-0-201-02988-8.
8. Pouly, Marc; Kohlas, Jürg (2011). Inferencia genérica: una teoría unificadora para el razonamiento automatizado . John Wiley e hijos. Capítulo 6. Álgebras de valoración para problemas de trayectoria, p. 223 en particular. ISBN 978-1-118-01086-0.
9. Jacek Jonczy (junio de 2008). "Problemas de caminos algebraicos" (PDF) . Archivado desde el original (PDF) el 21 de agosto de 2014 . Consultado el 20 de agosto de 2014 ., pag. 34
10. Felkin, M. (2007). Guillet, Fabrice; Hamilton, Howard J. (eds.). Medidas de Calidad en Minería de Datos - Estudios en Inteligencia Computacional . vol. 43. Springer, Berlín, Heidelberg. págs. 277–278. doi :10.1007/978-3-540-44918-8_12. ISBN 978-3-540-44911-9.
11. Brutscheck, M., Berger, S., Franke, M., Schwarzbacher, A., Becker, S.: Procedimiento de división estructural para un análisis de circuitos integrados eficiente. Conferencia irlandesa de sistemas y señales de IET (ISSC 2008), págs. 18-23. Galway, Irlanda, 18 y 19 de junio de 2008. [1]
12. "Tiwari, A. (2002). Semántica formal y métodos de análisis para modelos de flujo de estado de Simulink" (PDF) . sri.com . Consultado el 14 de abril de 2018 .
13. Hamon, G. (2005). "Una semántica denotacional para Stateflow" . Conferencia internacional sobre software integrado. Jersey City, Nueva Jersey: ACM. págs. 164-172. CiteSeerX 10.1.1.89.8817 . 
14. "Harel, D. (1987). Un formalismo visual para sistemas complejos. Ciencia de la programación informática, 231-274" (PDF) . Archivado desde el original (PDF) el 15 de julio de 2011 . Consultado el 7 de junio de 2011 .
15. "Alur, R., Kanade, A., Ramesh, S. y Shashidhar, KC (2008). Análisis simbólico para mejorar la cobertura de simulación de modelos Simulink/Stateflow. Conferencia internacional sobre software integrado (págs. 89–98). Atlanta, Georgia: ACM" (PDF) . Archivado desde el original (PDF) el 15 de julio de 2011.
16. Negro, 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 desde el original el 13 de octubre de 2018 . Consultado el 2 de noviembre de 2016 .
17. Anderson, James Andrés; Jefe, Thomas J. (2006). Teoría de autómatas con aplicaciones modernas. Prensa de la Universidad de Cambridge. págs. 105-108. ISBN 978-0-521-84887-9.
18. Hopcroft, John E. (1971). Un algoritmo n log n para minimizar estados en un autómata finito (PDF) (Informe técnico). vol. CS-TR-71-190. Universidad de Stanford.^{[ enlace muerto permanente ]}
19. 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 .
20. Edward F. Moore (1956). CE Shannon y J. McCarthy (ed.). "Experimentos Gedanken en máquinas secuenciales". Anales de estudios de matemáticas . Prensa de la Universidad de Princeton. 34 : 129-153.Aquí: Teorema 4, p.142.
21. Revuz, D. (1992). "Minimización de autómatas acíclicos en tiempo lineal". Informática Teórica . 92 : 181–189. doi :10.1016/0304-3975(92)90142-3.
22. Kaeslin, Hubert (2008). "Bits de salida combinatoria y tipo Mealy, Moore, Medvedev". Diseño de circuitos integrados digitales: de arquitecturas VLSI a fabricación CMOS . Prensa de la Universidad de Cambridge. pag. 787.ISBN _ 978-0-521-88267-5.
23. Diapositivas Archivado el 18 de enero de 2017 en Wayback Machine , Máquinas de estados finitos síncronas; Diseño y comportamiento , Universidad de Ciencias Aplicadas de Hamburgo , p.18
24. Ah, Alfred V .; Sethi, Ravi ; Ullman, Jeffrey D. (1986). Compiladores: principios, técnicas y herramientas (1ª ed.). Addison-Wesley . ISBN 978-0-201-10088-4.

Otras lecturas

General

• Sakarovich, Jacques (2009). Elementos de la teoría de los autómatas . Traducido del francés por Reuben Thomas. Prensa de la Universidad de Cambridge . ISBN 978-0-521-84425-3. Zbl  1188.68177.
• Wagner, F., "Software de modelado con máquinas de estados finitos: un enfoque práctico", Publicaciones Auerbach, 2006, ISBN 0-8493-8086-3 . 
• UIT-T, Recomendación Z.100 Lenguaje de especificación y descripción (SDL)
• Samek, M., Gráficos de estado prácticos en C/C++, CMP Books, 2002, ISBN 1-57820-110-1 . 
• Samek, M., Diagramas de estado UML prácticos en C/C++, segunda edición, Newnes, 2008, ISBN 0-7506-8706-1 . 
• Gardner, T., Gestión avanzada del estado Archivado el 19 de noviembre de 2008 en Wayback Machine , 2007
• Cassandras, C., Lafortune, S., "Introducción a los sistemas de eventos discretos". Kluwer, 1999, ISBN 0-7923-8609-4 . 
• Timothy Kam, Síntesis de máquinas de estados finitos: optimización funcional . Editores académicos de Kluwer, Boston 1997, ISBN 0-7923-9842-4 
• Tiziano Villa, Síntesis de Máquinas de Estados Finitos: Optimización Lógica . Editores académicos de Kluwer, Boston 1997, ISBN 0-7923-9892-0 
• Carroll, J., Long, D., Teoría de los autómatas finitos con una introducción a los lenguajes formales . Prentice Hall, Acantilados de Englewood, 1989.
• Kohavi, Z., Teoría de la conmutación y los autómatas finitos . McGraw-Hill, 1978.
• Gill, A., Introducción a la teoría de las máquinas de estados finitos . McGraw-Hill, 1962.
• Ginsburg, S., Introducción a la teoría de las máquinas matemáticas . Addison-Wesley, 1962.

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

• Arbib, Michael A. (1969). Teorías de autómatas abstractos (1ª ed.). Englewood Cliffs, Nueva Jersey: 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.
• Stand, Taylor L. (1967). Teoría de máquinas secuenciales y autómatas (1ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de tarjetas 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, Martín; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidad, complejidad y lenguajes y lógica: fundamentos de la informática teórica (2ª ed.). San Diego: Prensa académica, Harcourt, Brace & Company. ISBN 978-0-12-206382-4.
• Hopcroft, John; Ullman, Jeffrey (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas (1ª ed.). Misa de lectura: Addison-Wesley. ISBN 978-0-201-02988-8.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introducción a la teoría, los lenguajes y la computación de los autómatas (2ª ed.). Misa de lectura: Addison-Wesley. ISBN 978-0-201-44124-6.
• 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 y 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, Nicolás (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 autómatas y lenguajes formales (1ª ed.). Sudbury, MA: Jones y Bartlett. ISBN 978-0-7637-3834-1.
• Sipser, Michael (2006). Introducción a la Teoría de la Computación (2ª ed.). Boston Mass: Tecnología del curso Thomson. ISBN 978-0-534-95097-2.
• Madera, 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 abstractos en informática teórica.

• Gurevich, Yuri (julio de 2000). "Las máquinas de estados abstractos secuenciales capturan algoritmos secuenciales" (PDF) . Transacciones ACM sobre lógica computacional . 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.

• Stand, Taylor L. (1967). Teoría de máquinas secuenciales y autómatas (1ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de tarjetas de la Biblioteca del Congreso 67-25924.
• Stand, 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 tarjetas 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 tarjetas de la Biblioteca del Congreso 65-17394.

Procesos de cadena finita de Markov

"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 está en el estado s _i pasa a la siguiente parada en el estado s _j con probabilidad p _ij . Estas probabilidades se pueden exhibir en forma de una matriz de transición" (Kemeny (1959), p. 384)

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

• Stand, Taylor L. (1967). Teoría de máquinas secuenciales y autómatas (1ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de tarjetas 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, Nueva Jersey: Prentice-Hall, Inc. Número de catálogo de tarjetas de la Biblioteca del Congreso 59-12841.Capítulo 6 "Cadenas finitas de Markov".

enlaces externos

• Autómatas de estados finitos en Curlie
• Modelado de un comportamiento de IA simple usando una máquina de estados finitos Ejemplo de uso en videojuegos
• Descripción gratuita del Diccionario de informática en línea de máquinas de estados finitos
• Descripción del Diccionario NIST de algoritmos y estructuras de datos de máquinas de estados finitos
• Una breve descripción general de los tipos de máquinas de estados, comparando aspectos teóricos de las máquinas de estados Mealy, Moore, Harel y UML.