"SFSM" vuelve a dirigir aquí. Para la compañía ferroviaria italiana, consulte Circumvesuviana .
"Autómatas finitos" vuelve a dirigir aquí. Para el grupo electroindustrial, consulte Autómatas finitos (banda) .
Modelo matemático de computación
Clases de autómatas
(Al hacer clic en cada capa se obtiene un artículo sobre ese tema)
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 mediante 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 .
12.2 Máquinas de estados finitos (teoría de autómatas) en informática teórica
12.3 Máquinas de estados abstractos en informática teórica
12.4 Aprendizaje automático mediante algoritmos de estado finito
12.5 Ingeniería de hardware: minimización de estados y síntesis de circuitos secuenciales
12.6 Procesos de cadena de Markov finitos
13 Enlaces externos
Ejemplo: torniquete que funciona con monedas
Diagrama de estado de un torniquete
Un torniquete
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 los juegos mecánicos del parque de atracciones, 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 pase. 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 empuje 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:
Estado actual
Aporte
Estado siguiente
Producción
Bloqueado
moneda
Desbloqueado
Desbloquea el torniquete para que el cliente pueda pasar.
empujar
Bloqueado
Ninguno
Desbloqueado
moneda
Desbloqueado
Ninguno
empujar
Bloqueado
Cuando el cliente ha pasado, bloquea el torniquete.
La máquina de estado 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 causa 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 en 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 usa un sistema de audio para escuchar la radio (el sistema está en el estado "radio"), recibir un estímulo "siguiente" resulta en pasar a la siguiente estación. Cuando el sistema está en el estado "CD", el "siguiente" estímulo da como resultado que se mueva a la siguiente pista. Los 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 entrar al estado, y
una acción de salida: realizada al salir del estado.
Representaciones
Fig.1 Ejemplo de gráfico de estado UML (horno tostador)
Fig.2 Ejemplo de máquina de estado SDL
Fig.3 Ejemplo de una máquina simple de estados finitos
Para obtener una introducción, consulte el diagrama de estado .
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 de la acción completa no se describe directamente en la tabla y solo se puede agregar mediante notas al pie. [ se necesita más explicación ] Una definición de FSM que incluya la información completa de la acción es posible usando tablas de estado (ver también máquina virtual de estados finitos ).
Tabla de transición de estado
Estado actual
Aporte
Estado A
Estado B
Estado C
Entrada X
...
...
...
Entrada Y
...
Estado C
...
Entrada Z
...
...
...
Máquinas de estado UML
El lenguaje de modelado unificado tiene una notación para describir las máquinas de estado. Las máquinas de estado UML superan las limitaciones [ cita requerida ] de las máquinas tradicionales de estados finitos al tiempo que conservan sus principales beneficios. Las máquinas de estado UML introducen los nuevos conceptos de estados anidados jerárquicamente y regiones ortogonales , al tiempo que amplían la noción de acciones . Las máquinas de estado UML tienen las características de las máquinas Mealy y las máquinas Moore . Apoyan acciones que dependen tanto del estado del sistema como del evento desencadenante., como en las máquinas Mealy, así como las acciones de entrada y salida , que están asociadas con estados más que con transiciones, como en las máquinas de Moore. [ cita requerida ]
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 estado concurrente
decisión
SDL incorpora tipos de datos básicos denominados "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 requerida ]
Otros diagramas de estados
Hay 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, incluida 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, las máquinas de estados finitos se utilizan ampliamente en el modelado del comportamiento de las aplicaciones, el diseño de sistemas digitales de hardware , la ingeniería de software ,compiladores , protocolos de red y el estudio de la computación y los lenguajes.
Clasificación
Las máquinas de estados finitos se pueden subdividir en aceptores, clasificadores, transductores y secuenciadores. [6]
Aceptadores
Fig. 4: FSM del aceptador: analizando la cadena "agradable".
Fig. 5: Representación de un aceptador; este ejemplo muestra uno que determina si un número binario tiene un número par de ceros, donde S 1 es un estado de aceptación y S 2 es un estado de no aceptación .
Los aceptadores (también llamados detectores o reconocedores ) producen una salida binaria, indicando si la entrada recibida es aceptada o no. Cada estado de un aceptador es de aceptación o 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; de lo contrario, se rechaza. Como regla, la entrada es una secuencia de símbolos (caracteres); las acciones no se utilizan. El estado de inicio 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 "agradable". 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 aceptador que acepte exactamente ese conjunto. Por ejemplo, el conjunto de cadenas binarias con un número par de ceros es un lenguaje regular (ver 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 aceptadores son los idiomas regulares .
El problema de determinar el lenguaje aceptado por un aceptador dado es un ejemplo del problema de la ruta algebraica, en sí mismo una generalización del problema de la ruta más corta a gráficos con aristas ponderadas por los elementos de un semiring (arbitrario) . [8] [9] [ jerga ]
Un ejemplo de un estado de aceptación aparece en la Fig. 5: un autómata finito determinista (DFA) que detecta si la cadena de entrada binaria contiene un número par de ceros.
S 1 (que también es el estado de inicio) indica el estado en el que se ha introducido un número par de ceros. Por tanto, S 1 es un estado de aceptación. Este aceptador terminará 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
Artículo principal: transductor de estado finito
Fig.6 Transductor FSM: ejemplo de modelo de Moore
Fig.7 Transductor FSM: ejemplo de 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:
Máquina de moore
El FSM usa solo acciones de entrada, es decir, la salida depende solo del estado. La ventaja del modelo de Moore es una simplificación del comportamiento. Considere la puerta de un ascensor. La máquina de estado reconoce dos comandos: "command_open" y "command_close", que activan cambios de estado. La acción de entrada (E :) en el estado "Apertura" pone en marcha un motor que abre la puerta, la acción de entrada en el estado "Cerrando" pone en marcha un motor en la otra dirección cerrando 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 estado) la situación: "puerta abierta" o "puerta cerrada".
Máquina harinosa
El FSM también usa acciones de entrada, es decir, la salida depende de la entrada y el estado. El uso de Mealy FSM conduce a menudo a una reducción del número de estados. El ejemplo de la figura 7 muestra un FSM Mealy implementando el mismo comportamiento que en el ejemplo de Moore (el comportamiento depende del modelo de ejecución FSM implementado y funcionará, por ejemplo, para FSM virtual pero no para FSM impulsado por eventos ). Hay dos acciones de entrada (I :): "arrancar motor para cerrar la puerta si llega command_close" y "arrancar motor en la otra dirección para abrir la puerta si llega command_open". No se muestran los estados intermedios "apertura" y "cierre".
Secuenciadores
Los secuenciadores (también llamados generadores ) son una subclase de aceptores 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 las salidas del aceptador o del transductor. [6]
Determinismo
Una distinción adicional 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 dado. El algoritmo de construcción de powerset puede transformar cualquier autómata no determinista en un autómata determinista (generalmente más complejo) con idéntica funcionalidad.
Una máquina de estados finitos con un solo estado se denomina "FSM combinatoria". Solo permite acciones durante la transición a un estado. Este concepto es útil en los casos en que se requiere que varias máquinas de estados finitos trabajen juntas, y cuando es conveniente considerar una parte puramente combinatoria como una forma de FSM para adaptarse a las herramientas de diseño. [11]
Semántica alternativa
Hay otros conjuntos de semántica disponibles para representar máquinas de estado. Por ejemplo, existen herramientas para modelar y diseñar lógica para controladores integrados. [12] Combinan máquinas de estado jerárquicas (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, como las máquinas de estado 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 aceptador determinista de estados finitos es un quintuple , donde:
es el alfabeto de entrada (un conjunto finito no vacío de símbolos);
es un conjunto finito no vacío de estados;
es un estado inicial, un elemento de ;
es la función de transición de estado: (en un autómata finito no determinista sería , es decir , devolvería un conjunto de estados);
es el conjunto de estados finales, un subconjunto (posiblemente vacío) de .
Tanto para FSM deterministas como 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 las definiciones de máquinas de estado generales, pero menos útil cuando se transforma la máquina. Algunos algoritmos en su forma predeterminada pueden requerir funciones totales.
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. Es decir, cada lenguaje formal aceptado por una máquina de estados finitos es aceptado por tal tipo de máquina de Turing restringida, y viceversa. [dieciséis]
Un transductor de estado finito es un séxtuple , donde:
es el alfabeto de entrada (un conjunto finito no vacío de símbolos);
es el alfabeto de salida (un conjunto finito no vacío de símbolos);
es un conjunto finito no vacío de estados;
es el estado inicial, un elemento de ;
es la función de transición de estado: ;
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 solo 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 se conoce como semiautomatón o sistema de transición .
Si ignoramos el primer símbolo de salida de una máquina Moore , entonces se puede convertir fácilmente en una máquina Mealy equivalente a la salida configurando la función de salida de cada transición Mealy (es decir, etiquetando cada borde) con el símbolo de salida dado del destino Moore estado. La transformación inversa es menos sencilla porque un estado de máquina Mealy puede tener diferentes etiquetas de salida en sus transiciones entrantes (bordes). Cada uno de estos estados debe dividirse en varios estados de la máquina de Moore, uno por cada símbolo de salida de incidente. [17]
Mejoramiento
Artículo principal: minimización de DFA
Optimizar un FSM significa encontrar una máquina con el número mínimo 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 tiempo lineal. [21]
Implementación
Aplicaciones de hardware
Fig.9 El diagrama de circuito para un contador TTL de 4 bits , un tipo de máquina de estado
En un circuito digital , un FSM puede construirse 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 se conecta directamente a los flip-flops estatales, lo que minimiza el tiempo de retraso entre los flip-flops y la salida. [22] [23]
Mediante la codificación de estado para máquinas de estado de baja potencia 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 estado finito:
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
Compiladores y máquinas de estados finitos
Los autómatas finitos se utilizan a menudo en la interfaz de los compiladores de lenguajes de programación. Dicha interfaz 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 crea una secuencia de símbolos de lenguaje (como palabras reservadas, literales e identificadores) a partir de los cuales el analizador genera 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 estado abstracto (ASM)
Inteligencia artificial (IA)
Lenguaje de máquina de estado abstracto (AsmL)
Modelo de comportamiento
Comunicación de la máquina de estados finitos
Sistema de control
Mesa de control
Tablas de decisiones
DEVS : Especificación del sistema de eventos discretos
Máquina de estados finitos extendida (EFSM)
Máquina de estados finitos con ruta de datos
Modelo de Markov oculto
Secuencia de inicio
Síntesis FSM de baja potencia
Red de Petri
Autómata de empuje
Autómatas finitos cuánticos (QFA)
Lenguaje reconocible
SCXML
Semiautomatón
Acción de semigrupo
Lógica secuencial
Lenguaje de especificación y descripción
Diagrama de estado
Patrón de estado
Secuencia de sincronización
Monoide de transformación
Monoide de transición
Sistema de transición
Autómata de árbol
máquina de Turing
Máquina de estado UML
Secuencia de entrada / salida única (UIO)
Referencias
^ Wang, Jiacun (2019). Métodos formales en informática . Prensa CRC. pag. 34. ISBN 978-1-4987-7532-8.
^ "Máquinas de estado finito - Wiki brillante de matemáticas y ciencia" . shiny.org . Consultado el 14 de abril de 2018 .
^ Belzer, Jack; Holzman, Albert George; Kent, Allen (1975). Enciclopedia de Ciencias y Tecnología de la Computación . 25 . Estados Unidos: CRC Press. pag. 73. ISBN 978-0-8247-2275-3.
↑ a b Koshy, Thomas (2004). Matemáticas discretas con aplicaciones . Prensa académica. pag. 762. ISBN 978-0-12-421180-3.
^ 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 .
↑ a b Keller, Robert M. (2001). "Clasificadores, aceptores, transductores y secuenciadores" (PDF) . Ciencias de la Computación: de la abstracción a la implementación (PDF) . Universidad Harvey Mudd. pag. 480.
^ John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Lectura / MA: Addison-Wesley. ISBN 978-0-201-02988-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.
^ Jacek Jonczy (junio de 2008). "Problemas de ruta algebraica" (PDF) . Archivado desde el original (PDF) el 21 de agosto de 2014 . Consultado el 20 de agosto de 2014 ., pag. 34
^ Felkin, M. (2007). Guillet, Fabrice; Hamilton, Howard J. (eds.). Medidas de calidad en minería de datos - Estudios en inteligencia computacional . 43 . Springer, Berlín, Heidelberg. págs. 277–278. doi : 10.1007 / 978-3-540-44918-8_12 . ISBN 978-3-540-44911-9.
^ Brutscheck, M., Berger, S., Franke, M., Schwarzbacher, A., Becker, S .: Procedimiento de división estructural para un análisis IC eficiente. IET Irish Signals and Systems Conference, (ISSC 2008), págs. 18–23. Galway, Irlanda, 18 a 19 de junio de 2008. [1]
^ "Tiwari, A. (2002). Métodos de análisis y semántica formal para modelos de flujo de estado de Simulink" (PDF) . sri.com . Consultado el 14 de abril de 2018 .
^ Hamon, G. (2005). Una semántica denotacional para Stateflow . Congreso Internacional de Software Embebido. Jersey City, Nueva Jersey: ACM. págs. 164-172. CiteSeerX 10.1.1.89.8817 .
^ "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 .
^ 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, GA: ACM.
^ Black, Paul E (12 de mayo de 2008). "Máquina de estado finito" . 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 .
^ Anderson, James Andrew; Jefe, Thomas J. (2006). Teoría de los autómatas con aplicaciones modernas . Prensa de la Universidad de Cambridge. págs. 105-108. ISBN 978-0-521-84887-9.
^ Hopcroft, John E. (1971). Un algoritmo n log n para minimizar estados en un autómata finito (PDF) (Informe técnico). CS-TR-71-190. Universidad de Stanford.[ enlace muerto permanente ]
^ Almeida, Marco; Moreira, Nelma; Reis, Rogerio (2007). Sobre el desempeño de los algoritmos de minimización de autómatas (PDF) (Informe técnico). DCC-2007-03. Porto Univ. Archivado desde el original (PDF) el 17 de enero de 2009 . Consultado el 25 de junio de 2008 .
^ Edward F. Moore (1956). CE Shannon y J. McCarthy (ed.). "Experimentos de Gedanken en máquinas secuenciales". Anales de estudios matemáticos . Prensa de la Universidad de Princeton. 34 : 129-153. Aquí: Teorema 4, p.142.
^ 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 .
^ Kaeslin, Hubert (2008). "Mealy, Moore, tipo Medvedev y bits de salida combinatoria" . Diseño de circuitos integrados digitales: desde arquitecturas VLSI hasta fabricación CMOS . Prensa de la Universidad de Cambridge. pag. 787. ISBN 978-0-521-88267-5.
^ Diapositivas archivadas el 18 de enero de 2017 en Wayback Machine , Synchronous Finite State Machines; Diseño y comportamiento , Universidad de Ciencias Aplicadas de Hamburgo , p.18
^ 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.
Otras lecturas
General
Sakarovitch, Jacques (2009). Elementos de la teoría de 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 de 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., Gráficos de estado prácticos de UML en C / C ++, 2da edición , Newnes, 2008, ISBN 0-7506-8706-1 .
Gardner, T., Gestión avanzada del estado , 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 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., Switching and Finite Automata Theory . 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 la máquina matemática . Addison-Wesley, 1962.
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, Nueva Jersey: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
Bobrow, Leonard S .; Arbib, Michael A. (1974). Matemáticas discretas: Álgebra aplicada para informática y 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 los autómatas (1ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de la tarjeta 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.
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.
Hopkin, David; Moss, Barbara (1976). Autómatas . Nueva York: Elsevier North-Holland. 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.
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 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 estado abstractas en informática teórica
Gurevich, Yuri (julio de 2000). "Máquinas de estado abstracto secuencial capturan algoritmos secuenciales" (PDF) . Transacciones ACM en 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 estado finito
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 los autómatas (1ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de la tarjeta 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 tarjeta 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 tarjeta de la Biblioteca del Congreso 65-17394.
Procesos finitos de la cadena 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 1 , s 2 , ..., s r . ... si está en el estado s i pasa a la siguiente parada al 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 de cadena de Markov finitos también se conocen como subdesplazamientos de tipo finito .
Booth, Taylor L. (1967). Máquinas secuenciales y teoría de los autómatas (1ª ed.). Nueva York: John Wiley and Sons, Inc. Número de catálogo de la tarjeta 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 la tarjeta de la Biblioteca del Congreso 59-12841. Capítulo 6 "Cadenas de Markov finitas".
enlaces externos
Wikimedia Commons tiene medios relacionados con la máquina de estados finitos .
Autómatas de estado finito en Curlie
Modelado de un comportamiento de IA simple usando una máquina de estados finitos Ejemplo de uso en videojuegos
Diccionario gratuito en línea de la descripción de las máquinas de estado finito
Descripción del Diccionario NIST de Algoritmos y Estructuras de Datos de Máquinas de Estado Finito
Una breve descripción de los tipos de máquinas de estado , comparando aspectos teóricos de las máquinas de estado de Mealy, Moore, Harel y UML.
vtmiElectrónica digital
Componentes
Transistor
Resistor
Inductor
Condensador
Electrónica impresa
Placa de circuito impreso
Circuito electrónico
Chanclas
Celda de memoria
Lógica combinacional
Lógica secuencial
Puerta lógica
Circuito booleano
Circuito integrado (IC)
Circuito integrado híbrido (HIC)
Circuito integrado de señal mixta
Circuito integrado tridimensional (3D IC)
Lógica acoplada por emisor (ECL)
Dispositivo lógico programable borrable (EPLD)
Matriz de macroceldas
Matriz lógica programable (PLA)
Dispositivo lógico programable (PLD)
Lógica de matriz programable (PAL)
Lógica de matriz genérica (GAL)
Dispositivo lógico programable complejo (CPLD)
Matriz de puertas programables en campo (FPGA)
Matriz de objetos programables en campo (FPOA)
Circuito integrado de aplicación específica (ASIC)
Unidad de procesamiento de tensor (TPU)
Teoría
Señal digital
álgebra de Boole
Síntesis lógica
Lógica en informática
Arquitectura de Computadores
Señal digital
Procesamiento de señales digitales
Minimización de circuitos
Teoría del circuito de conmutación
Equivalente de puerta
Diseño
Síntesis lógica
Lugar y ruta
Colocación
Enrutamiento
Nivel de transferencia de registro
Lenguaje de descripción de hardware
Síntesis de alto nivel
Comprobación de equivalencia formal
Lógica sincrónica
Lógica asincrónica
Máquina de estados finitos
Máquina de estado jerárquica
Aplicaciones
Hardware de la computadora
Aceleracion de hardware
Audio digital
radio
Fotografía digital
Telefono digital
Video digital
cine
televisión
Literatura electrónica
Problemas de diseño
Metaestabilidad
Pulso runt
Categorías :
Autómatas finitos
Categorías ocultas:
CS1: valor de volumen largo
Todos los artículos con enlaces externos muertos
Artículos con enlaces externos muertos de octubre de 2017
Artículos con enlaces externos permanentemente inactivos
Vínculos de retorno de la plantilla de archivo web
Artículos con breve descripción
La descripción breve es diferente de Wikidata
Utilice fechas dmy de enero de 2020
Artículos de Wikipedia que necesitan aclaración a partir de marzo de 2021
Todos los artículos con declaraciones sin fuente
Artículos con declaraciones sin fuente de marzo de 2021
Artículos con declaraciones sin fuente de enero de 2017
Todos los artículos que son demasiado técnicos
Artículos de Wikipedia que son demasiado técnicos a partir de enero de 2017
Todos los artículos que necesitan la atención de un experto
Artículos que necesitan la atención de un experto a partir de enero de 2017
El enlace de la categoría Commons está en Wikidata