Aplicación práctica de máquinas de estado finito

Estoy buscando aplicaciones prácticas de máquinas de estado finito como máquinas DFA, NFA, Moore, Mealy ...

Sería útil si alguien señalara ejemplos del kernel de Linux. Sé que DFA se usa en la coincidencia de cadenas como el algoritmo KMP.

¿Cuál es el significado de las máquinas NFA, Moore y Mealy?

Cada vez que realiza una búsqueda (particularmente una "búsqueda de patrones") en su editor / herramienta favorita, el patrón se traduce en alguna forma de máquina de estados finitos, que hace la coincidencia.

La parte de análisis léxico de su compilador / intérprete (sí, incluso su shell) es de nuevo un autómata finito que coincide con palabras clave y otros tokens reconocidos por el idioma.

Cualquier máquina expendedora es un autómata finito que toma monedas de diferentes denominaciones y reconoce cuándo se ingresó la cantidad correcta (OK, las máquinas expendedoras de hoy probablemente tienen una pequeña CPU dentro para hacer la suma, pero el resultado final es el mismo).

(los conceptos de) DFA / NFA tienen algunas aplicaciones en el campo de los compiladores y en la construcción de analizadores sintácticos. También se utilizan para identificar cadenas de acuerdo con expresiones regulares (es decir, buscar "patrones" en la web o en bases de datos)

Las máquinas Moore / Mealy son DFA que también han salido en cualquier momento del reloj. Esos tienen MUCHAS aplicaciones. De hecho, cualquier CPU, computadora, teléfono celular, reloj digital e incluso su lavadora tienen algún tipo de máquina de estado finito que lo controla.

Tal vez debería dejarlo claro: cualquier "computadora" es básicamente una máquina de estados finitos.

Una aplicación importante es el modelado de sistemas. Esencialmente, los sistemas de software simples se pueden modelar como máquinas de estado finito. (Por software simple, me refiero a los idiomas que se pueden representar usando expresiones regulares). Hay muchos de estos sistemas "simples", las máquinas expendedoras son ejemplos (como se indica en vzn).

Al encontrar la intersección de dos máquinas de estados finitos, puede diseñar de manera muy simple sistemas concurrentes que intercambian mensajes, por ejemplo. Como ejemplo, el semáforo es un sistema que consta de múltiples subsistemas (los diferentes semáforos) que funcionan simultáneamente.

Eche un vistazo a estos ejemplos: http://www.site.uottawa.ca/~bochmann/SEG-2106-2506/Notes/LTSA-examples/examples/

Necesitará tener un analizador LTSA para ejecutar estos ejemplos. http://www.doc.ic.ac.uk/ltsa/

Heres una muy buena referencia en línea sobre FSMs y teoría relacionada, 75p, con muchos diagramas. tiene muchas aplicaciones después de la sección de teoría media, y también en muchos ejercicios con aplicaciones de muestra, por ejemplo, p485:

ch12. Máquinas de estado finito por Keller, Harvey Mudd College, CS60 textbook / CS, introducción a la abstracción

Las aplicaciones son extremadamente diversas. Por ejemplo, del libro:

• clasificación de números
• ver con temporizador
• máquina expendedora
• semáforo
• escáner de código de barras
• bomba de gas

Sec. 12.4 Construcciones EE ej.

• elementos lógicos
• cuantización de reloj
• cerradura de combinación
• chancletas
• sumadores
• registros
• autobuses / multiplexación

Los FSM también se utilizan en la detección de voz para encontrar fonemas , uno de los principales puntos de aplicación de esta excelente biblioteca en línea que tiene más detalles en las páginas de manual y la documentación: la biblioteca en línea de FSM de AT&T . consulte la sección "Biblioteca FSM y aplicaciones de procesamiento de voz" (que también enumera algunas "aplicaciones" más abstractas / teóricas)

etc!

Yo uso máquinas de estado cuando escribo controladores de dispositivos. Tenga en cuenta que las máquinas de estado grandes pueden volverse difíciles de manejar. Considere usar este conjunto de macros ( https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at ) ... de esa manera las transiciones se vuelven tan simples que usted no Incluso necesita un diagrama de estado. Esto se debe a que las macros le permiten escribir su código de máquina de estado como si fuera un código estructurado. Escribí la Biblioteca Transceptor de Cisco para el Nexus 7000 usando estas macros.

En la práctica, lo verá explícitamente como una variable de estado entero (generalmente llamada 'estado') que representa una máquina de estado muy gruesa que representa qué acciones puede llamar el usuario de un objeto. Suele ser una enumeración con valores como: {no inicializado, inicializado, ..., detenido}. Las máquinas de estado a menudo son explícitas cuando se analizan datos, y se indicarán mediante una instrucción switch en un ciclo while donde, en la parte superior del ciclo, se obtiene el siguiente carácter. En particular, si el análisis tiene una gramática regular, a menudo se usa un FSM exacto sin otras características. Si está en un lenguaje que admite llamadas de cola, los FSM generalmente se exhiben por recursión mutua (lo que puede hacer que el código se lea como una especificación de pseudocódigo muy clara). Una característica realmente útil de un FSM es la capacidad de operar simultáneamente, ya que solo necesita recordar el estado actual, en lugar de una pila de ejecución completa. (es decir, cambio de contexto entre millones de instancias de máquinas de estado).