Я знаю, что мы можем минимизировать DFA, находя и объединяя эквивалентные состояния, но почему мы не можем сделать то же самое с NFA? Я не ищу доказательств или чего-то в этом роде - если только доказательство не проще для понимания. Я просто хочу интуитивно понять, почему минимизация NFA так сложна, чем минимизация DFA.
14
Вы спрашивали об интуитивном восприятии.
В DFA любой заданный входной префикс может достигать не более одного состояния. Затем можно объединить пары состояний, которые неразличимы для любого суффикса. Состояния, которые можно различить по некоторому суффиксу, не могут быть объединены. Это приводит к минимальному автомату, который изоморфен всем другим минимальным автоматам.
источник
см. также этот вопрос TCS.se для вычисления минимального NFA для DFA
источник