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 é.

complexity-theory finite-automata nondeterminism Duncan
fonte

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. $\{ ab, ac, bc, ba, ca, 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.

$pq$ $p$ $P$ $P$ $q$ $Q$ $P$ $q$ $P$ $Q$ .

$n$ $2^n$ 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ção $O(ns \log n)$ 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

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

Respostas: