Comecei a ler sobre teoria da computação. Se compararmos o que é mais poderoso (na aceitação de strings), ambos são iguais. Mas e quanto à eficiência? O DFA será rápido em comparação com o NFA, pois possui apenas uma borda de saída e não haverá ambiguidade. Mas no caso da NFA, temos que verificar todos os casos possíveis e isso certamente leva tempo. Então, podemos dizer que o DFA é mais eficiente que o NFA?
Mas, minha outra parte do cérebro também pensa que a NFA existe apenas em teoria, portanto não podemos comparar sua eficiência com a DFA.
Em termos de potência, eles são equivalentes, como você disse, e existe um algoritmo (construção de subconjunto) para converter um NFA em um DFA equivalente. Como você pode dizer pelo nome do algoritmo, ele constrói subconjuntos de estados do NFA. Se o seu NFA possui estados, o algoritmo pode gerar um DFA comn estados, mas esse é um limite superior. Às vezes, o número de estados não muda nem reduz. Portanto, na prática, importa menos sobre qual deles usar.2n
A correspondência do DFA é linear no tamanho da sequência de entrada. A correspondência NFA envolve retroceder para que os NFAs trabalhem mais. Assim, os DFAs são mais eficientes.
fonte
Apenas adicionando às respostas acima:
Os NFAs podem ser computacionalmente mais eficientes que os DFAs, no sentido de que podem ser simulados em um processador paralelo.
BTW: Vejo pessoas dizendo que os NFAs não podem existir na realidade. Eu peço desculpa mas não concordo. Um computador com um grande número de processadores pode executar muitas tarefas em paralelo e pode ser considerado como uma máquina não determinística. Pode-se atribuir cada ramo da computação a um novo processador e interromper todos eles sempre que um deles aceitar.
fonte
fonte
Como outros observaram, você precisa definir o que significa "eficiência". Para ilustrar isso, dou um modelo razoável com uma resposta diferente.
Procurando apenas o (s) modelo (s) de autômatos, que estão ignorando em particular como você os implementaria em máquinas reais, a medida de eficiência óbvia é "número de transições realizadas em uma execução (mais curta) de aceitação".
fonte
Tecnicamente falando, um NFA é um conceito mais geral que um DFA, pois não é necessário usar o não-determinismo. Em outras palavras: todo DFA é um NFA. Nessa perspectiva, existe para todos os idiomas um NFA que seja pelo menos tão eficiente quanto o DFA mais eficiente, para qualquer medida de eficiência que você preferir.
Fora isso, eu concordo com Raphael que depende muito do que você quer dizer com eficiência e na implementação.
fonte
Como sabemos sobre o Automata, isto é, uma máquina que pode executar qualquer ação sem qualquer poder humano ou sem a participação direta do homem. por exemplo: máquina de lavar. Autômatos finitos significa que sabemos o estado de execução de tarefas por máquina, como 1 pressionar ON 2 pressionar OFF, portanto, existem apenas 2 estados, ou seja, chamados autômatos finitos. Agora venha para o DFA, isto é, autômatos finitos determinísticos. formalmente significa que podemos determinar facilmente estados em que não há ambiguidade e informalmente ele precisa de apenas 1 transição permitida em 1 símbolo. AFN: autômatos finitos não determinísticos. é necessário mais tempo para calcular o estado real e existe ambiguidade e informa informalmente que há várias transições permitidas em um símbolo. no caso de tempo para chegar ao destino, o NFA leva mais tempo que o DFA, mas pode carregar mais dados que o DFA. * O DFA e o NFA têm o mesmo poder de reconhecer a sequência. obrigado .. Deepali kaushik
fonte