¿Por qué la minimización de NFA es un problema difícil cuando la minimización de DFA no lo es?

Sé que podemos minimizar los DFA al encontrar y fusionar estados equivalentes, pero ¿por qué no podemos hacer lo mismo con los NFA? No estoy buscando una prueba ni nada de eso, a menos que una prueba sea más fácil de entender. Solo quiero entender intuitivamente por qué la minimización de NFA es tan difícil cuando la minimización de DFA no lo es.

Para DFA hay una buena estructura algebraica que determina qué estados pueden ser equivalentes, la equivalencia de Myhill-Nerode en las cadenas está relacionada con la minimización de DFA.

Para NFA, la situación es complicada ya que no existe un NFA mínimo único en general.

Aquí hay un ejemplo para el lenguaje finito . Los dos autómatas son ambos mínimos de estado. El ejemplo es del artículo Una nota sobre autómatas no deterministas mínimos de Arnold, Dicky y Nivat.$\{ ab, ac, bc, ba, ca, cb\}$

Esta respuesta intenta expresar el hecho de que los dos problemas son "técnicamente" diferentes. Consulte la respuesta de vzn para obtener detalles sobre cómo los problemas difieren en la complejidad computacional.

Preguntaste sobre una toma intuitiva.

En un DFA, cualquier prefijo de entrada dado solo puede alcanzar como máximo un estado. Entonces, uno puede fusionar pares de estados que son indistinguibles para cualquier sufijo. Los estados que pueden distinguirse por algún sufijo no pueden fusionarse. Esto conduce a un autómata mínimo que es isomorfo a todos los demás autómatas mínimos.

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

$n$$2^n$

$O(ns \log n)$

vea también esta pregunta de TCS.se que calcula el NFA mínimo para un DFA