Pourquoi la minimisation NFA est-elle un problème difficile alors que la minimisation DFA ne l'est pas?

Je sais que nous pouvons minimiser les DFA en trouvant et en fusionnant des états équivalents, mais pourquoi ne pouvons-nous pas faire de même avec les NFA? Je ne cherche pas une preuve ou quelque chose comme ça - à moins qu'une preuve soit plus simple à comprendre. Je veux juste comprendre intuitivement pourquoi la minimisation NFA est si difficile quand la minimisation DFA ne l'est pas.

Pour DFA, il existe une belle structure algébrique qui détermine quels états peuvent être équivalents, l'équivalence Myhill-Nerode sur les chaînes est liée à la minimisation de DFA.

Pour la NFA, la situation est compliquée car il n'y a pas de NFA minimal unique en général.

Voici un exemple pour le langage fini . Les deux automates ont tous deux un état minimal. L'exemple est tiré de l'articleUne note sur les automates minimaux non déterministesd'Arnold, Dicky et Nivat.$\{ ab, ac, bc, ba, ca, cb\}$

Cette réponse tente d'exprimer le fait que les deux problèmes sont "techniquement" différents. Voir la réponse de vzn pour plus de détails sur la différence des problèmes de complexité de calcul.

Vous avez demandé une prise intuitive.

Dans un DFA, un préfixe d'entrée donné ne peut atteindre au plus qu'un état. On peut alors fusionner ensemble des paires d'états qui ne peuvent être distingués pour aucun suffixe. Les États qui peuvent être distingués par un suffixe ne peuvent pas être fusionnés. Cela conduit à un automate minimal isomorphe à tous les autres automates minimaux.

$pq$$p$$P$$P$$q$$Q$$P$$q$$P$$Q$ sous-ensembles d'états .

$n$$2^n$

la question ne définit pas «dur» alors qu'il y a un sens technique du mot dans TCS. dans un sens, ni l'un ni l'autre n'est "difficile" (minimisant les DFA ou les NFA) car de nombreux algorithmes existent pour les deux. cependant, un autre angle à ce sujet. La minimisation DFA est exécutable$O(ns \log n)$où s est le nombre d'états, c'est-à-dire PTime. La minimisation NFA a été prouvée complète sur PSpace. La minimisation NFA n'est pas dans PTime à moins que P = PSpace, qui est largement considéré comme faux.

voir aussi cette question TCS.se calculant le NFA minimal pour un DFA