Não determinísticos máquinas de estados finitos no desenvolvimento de software?

Question

Recentemente eu estive pensando sobre máquinas de estados finitos (FSMs), e como eu iria implementá-los em software (linguagem de programação não importa).

O meu entendimento é que máquinas de estado determinísticos estão em uso generalizado (Analisa / lexers, compiladores e assim por diante), mas o que é o problema com máquinas de estado não-deterministas ?

Eu sei que é possível converso todas as máquinas de estado não-determinísticos para os deterministas (mesmo programaticamente). Isso não é o meu ponto. Imagino também que máquinas de estado não-determinísticos são muito mais complicadas de implementar.

De qualquer forma, isso faz qualquer sentido de implementar uma máquina de estado não-determinista? Há aplicações especiais que eu não sei sobre? Quais poderiam ser as razões para fazer isso? máquinas de estado não-deterministas talvez otimizados e especializados são mais rápidos?

Answer 1

motores expressão mais regulares usar não autômatos -deterministic uma vez que oferecem muita flexibilidade maior. DFAs são muito mais restrito. Ter um olhar para algumas implementações e você vai ver isso. Microsoft mesmo sublinha este fato em sua documentação do rel .NET Regex classe:

O mecanismo de expressão regular Framework é uma correspondência de expressão regular retrocesso que incorpora um não-determinístico Finitos Autómato motor tradicional (NFA) tal como o utilizado por Perl, Python, Emacs, e Tcl.

Matching comportamento (primeiro parágrafo) -. este artigo também oferece uma justificativa para o emprego de um NFA ao invés do DFA mais eficiente

Answer 2

Como você sabe, NFAs e DFAs são computacionalmente equivalente. É um dos primeiros teoremas em autômatos teoria. Existem algoritmos para converter uma a outra (ao contrário Pushdown ou máquinas de Turing).

Então. Por um sobre o outro? Porque a representação de um determinado problema com a NFA é muito mais fácil do que o DFA equivalente.

Editar: em termos de realmente calcular a máquina, DFAs estão indo para ir mais rápido, porque eles não têm a recuar. Mas eles vão ter mais memória para representar. (Mem vs tradeoff CPU)

Answer 3

Meu conselho = dar uma olhada no manual para Adrian Thurstons Ragel .

Não são simples, formas de gerar um DFA diretamente, mas eu acredito que eles suportam apenas um número limitado de operadores - basicamente as EBNF suspeitos do costume. Ragel usa métodos não-determinísticos para compor autômatos complexo das mais simples, em seguida, utiliza a eliminação epsilon e minimização para criar eficiente autômatos determinista. Não importa quantos operadores estranho que você precisa, a conversão para um autômato determinístico mínimo é sempre o mesmo, e cada implementação operador é mantida simples usando métodos não-determinísticos.

Answer 4

O Viterbi algoritmo opera em Hidden Markov Models por tratá-los muito parecido com um NFA. Não inteiramente idêntica, mas certamente análoga.

Eles são úteis em aplicações como voz e reconhecimento de texto.

Answer 5

Muitas vezes é muito mais fácil criar um NFA e, em seguida, trabalhar com ele (a única diferença é que você mantenha um conjunto de estados em vez de um estado). Se você quiser tê-lo rápido, você pode fazer DFA, mas não se esqueça, que o tempo para fazê-lo é exponencial (por causa do autômato resultante pode ser exponencialmente maior!).

Por outro lado, se você quiser fazer uma linguagem de complemento, você não tem escolha, você precisa de um det. variante.

É a razão pela qual a negação está em nenhum dos regulares-expressão-motor, apenas em aulas ([^ ...]), onde você pode ter certeza que o autômato é determinista.

Answer 6

me corrija se eu estiver errado, mas a partir de minha classe compiladores Eu me lembro que às vezes você simplesmente não pode usar DFA, uma vez que levaria a uma "explosão" de estados.

Answer 7

Eu acho que a principal razão para a escolha de um autômato finito não-determinístico seria realmente começar a partida de volta escolhido. É provável muito mais difícil fazê-lo com uma versão determinista.

Se tudo que você quer saber é se eles combinam ou não, e há outros detalhes, eu acho que compilar para baixo para um autômato finito seria melhor.

Answer 8

cayugas utiliza não-determinística máquinas de estados finitos sob o capô para eventos complexos em processamento. Bem, parece que eles chamam de "Stateful Publish / Subscribe para monitoramento de eventos", mas eu acredito que é CEP.

Eu acredito que alguns de seus papéis até mesmo discutir por que eles estão usando um modelo de autômatos. Você pode querer picar em torno de seu site.

... Cayuga autômatos, prorrogado a partir de autômatos finitos não determinística padrão.