Aplicação prática de máquinas de estados finitos

Estou procurando aplicações práticas de máquinas de estado finito como máquinas DFA, NFA, Moore, Mealy ...

Seria útil se alguém apontasse para exemplos do Linux Kernel. Eu sei que o DFA é usado na correspondência de strings como o algoritmo KMP.

Qual é o significado das máquinas NFA, Moore e Mealy?

Cada vez que você faz uma pesquisa (particularmente uma "pesquisa de padrão") em seu editor / ferramenta favorito, o padrão é traduzido em alguma forma de máquina de estados finitos, que faz a correspondência.

A parte da análise lexical do seu compilador / intérprete (sim, até o seu shell) é novamente um autômato finito que corresponde a palavras-chave e outros tokens reconhecidos pelo idioma.

Qualquer máquina de venda automática é um autômato finito que recebe moedas de diferentes denominações e reconhece quando a quantidade correta foi inserida (OK, as máquinas de venda atuais hoje provavelmente têm uma pequena CPU dentro da adição, mas o resultado final é o mesmo).

(os conceitos de) DFA / NFA têm algumas aplicações no campo de compiladores e na construção de analisadores. Eles também são usados ​​para identificar seqüências de caracteres de acordo com expressões regulares (ou seja, pesquisando "padrões" na Web ou em bancos de dados)

Máquinas Moore / Mealy, são DFAs que também saem a qualquer momento. Aqueles têm ABUNDÂNCIA de aplicações. De fato, qualquer CPU, computador, telefone celular, relógio digital e até sua máquina de lavar têm algum tipo de máquina de estado finito, que a controla.

Talvez eu deva deixar claro: qualquer "computador" é basicamente uma máquina de estados finitos.

Uma aplicação importante é a modelagem de sistemas. Essencialmente, sistemas simples de software podem ser modelados como Máquinas de Estado Finito. (Por software simples, quero dizer idiomas que podem ser representados usando expressões regulares). Existem muitos desses sistemas "simples", as máquinas de venda automática são exemplos (como vzn indicado).

Ao encontrar a interseção de duas máquinas de estados finitos, é possível projetar de uma maneira muito simples sistemas concorrentes que trocam mensagens, por exemplo. Como exemplo, o semáforo é um sistema que consiste em vários subsistemas (os diferentes semáforos) que funcionam simultaneamente.

Veja estes exemplos: http://www.site.uottawa.ca/~bochmann/SEG-2106-2506/Notes/LTSA-examples/examples/

Você precisará do analisador LTSA para executar esses exemplos. http://www.doc.ic.ac.uk/ltsa/

aqui está uma referência on-line muito boa sobre FSMs e teoria relacionada, 75p, com muitos diagramas. tem muitas aplicações após a seção da teoria do meio e também em muitos exercícios com aplicações de exemplo, por exemplo, p485:

ch12. Máquinas de Estado Finito de Keller, Harvey Mudd College, livro CS60 / CS, introdução à abstração

aplicações são extremamente diversas. por exemplo, do livro:

• classificação numérica
• assistir com temporizador
• Maquina de vendas
• semáforo
• leitor de códigos de barra
• bomba de gasolina

sec 12.4 construções EE, por exemplo

• elementos lógicos
• quantização do relógio
• fechadura de combinação
• sandálias de dedo
• adicionadores
• registra
• barramentos / multiplexação

Os FSMs também são usados ​​na detecção de fala para encontrar fonemas , um dos principais pontos de aplicação desta excelente biblioteca on-line, que possui mais detalhes nas páginas de manual e na documentação: biblioteca on-line FSM da AT&T . consulte a seção "Biblioteca FSM e aplicativos de processamento de fala" (que também lista algumas "aplicações" abstratas / teóricas)

etc!

Eu uso máquinas de estado ao escrever drivers de dispositivo. Cuidado que grandes máquinas de estado podem se tornar pesadas. Considere usar este conjunto de macros ( https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at ) ... para que as transições se tornem tão simples que você não ainda precisa de um diagrama de estado. Isso ocorre porque as macros permitem escrever o código da máquina do estado como se fosse um código estruturado. Escrevi a biblioteca do transceptor da Cisco para o Nexus 7000 usando essas macros.

Na prática, você a verá explicitamente como uma variável de estado inteiro (geralmente chamada de 'estado') que representa uma máquina de estado muito grosseira que representa quais ações podem ser chamadas pelo usuário de um objeto. Geralmente é uma enumeração com valores como: {não inicializado, inicializado, ..., parado}. Máquinas de estado geralmente são explícitas ao analisar dados e serão representadas por uma instrução switch em um loop while, onde, na parte superior do loop, o próximo caractere é obtido. Em particular, se a análise tiver uma gramática regular, um FSM exato sem outros recursos será frequentemente usado. Se você estiver em um idioma que suporte chamadas de chamada, os FSMs geralmente serão exibidos por recursão mútua (que pode fazer com que o código seja lido como uma especificação de pseudocódigo muito clara). Um recurso realmente útil de um FSM é a capacidade de operar simultaneamente, porque você só precisa se lembrar do estado atual, e não de uma pilha de execução inteira. (ou seja: alternância de contexto entre milhões de instâncias de máquinas de estado).