Por que a minimização de NFA é um problema difícil quando a minimização de DFA não é?

14

Sei que podemos minimizar os DFAs localizando e mesclando estados equivalentes, mas por que não podemos fazer o mesmo com os NFAs? Não estou procurando uma prova ou algo assim - a menos que uma prova seja mais simples de entender. Eu só quero entender intuitivamente por que a minimização do NFA é tão difícil quando a minimização do DFA não é.

Duncan
fonte

Respostas:

8

Para o DFA, existe uma boa estrutura algébrica que determina quais estados podem ser equivalentes; a equivalência de Myhill-Nerode nas cadeias está relacionada à minimização do DFA.

Para a NFA, a situação é complicada, pois geralmente não existe uma NFA mínima única .

Aqui está um exemplo para a linguagem finita . Os dois autômatos são mínimos no estado. O exemplo é do artigo Uma nota sobre autômatos não determinísticos mínimos de Arnold, Dicky e Nivat.{umab,umac,bc,buma,cuma,cb}

dois NFA para o mesmo idioma

Essa resposta tenta expressar o fato de que os dois problemas são "tecnicamente" diferentes. Veja a resposta de vzn para detalhes de como os problemas diferem na complexidade computacional.

Hendrik Jan
fonte
8
Nem o problema do caminho mais curto nem o da extensão mínima (sempre) têm soluções únicas, mas ainda são eficientemente solucionáveis.
Raphael
5

Você perguntou sobre uma tomada intuitiva.

Em um DFA, qualquer prefixo de entrada especificado pode atingir apenas no máximo um estado. Pode-se então mesclar pares de estados indistinguíveis de qualquer sufixo. Estados que podem ser distinguidos por algum sufixo não podem ser mesclados. Isso leva a um autômato mínimo que é isomórfico para todos os outros autômatos mínimos.

pqpPPqQPqPQ .

n2n subconjuntos de estados torna mais difícil lidar com a minimização de NFA no pior dos casos.

András Salamon
fonte
1

a questão não define "difícil", enquanto existe um sentido técnico da palavra no TCS. em certo sentido, nenhum dos dois é "rígido" (minimizando DFAs ou NFAs) porque existem muitos algoritmos para ambos. no entanto, outro ângulo sobre isso. A minimização do DFA tem tempo de execuçãoO(nsregistron)onde s é o número de estados, ou seja, PTime. A minimização de NFA foi comprovada como completa no PSpace. A minimização de NFA não está no PTime, a menos que P = PSpace, que se acredita amplamente não seja verdadeiro.

veja também esta pergunta TCS.se que calcula o NFA mínimo para um DFA

vzn
fonte
Não sei definir muito, mas quis dizer que não existe um algoritmo eficiente para resolvê-lo.
Duncan
@ Duncan ok, então você usou realmente a palavra no sentido técnico. portanto, há alguns esclarecimentos sobre a dureza técnica. no CS, "eficiente" também é um termo técnico adotado / definido como o mesmo do PTime. portanto, sua pergunta está relacionada a uma importante questão aberta no TCS - é amplamente suspeito / formulado que a minimização de NFA (junto com todos os problemas completos do PSpace) é realmente "difícil", ou seja, não em P, mas ainda não está comprovada.
vzn