Алгоритм минимизации Хопкрофта предполагает полный DFA, в котором каждое состояние имеет переход по каждому символу в алфавите.
Обычно используют неполные DFA, в которых пропущенные переходыпозволил.Технически, это NFA (хотя это полностью детерминировано).В отличие от DFA, NFA позволяет символу алфавита создавать набор возможных переходов из данного состояния, и этот набор может быть пустым, в этом случае NFA останавливается.(DFA останавливается только при достижении конца ввода.)
В целях минимизации обычно добавляется неприемлемое состояние «приемника», которое имеет переход к себе на каждом входном символе.Все «пропущенные» переходы могут быть заменены переходом в состояние стока, что делает автомат завершенным.(На практике, конечно, предпочтительнее использовать автомат, который немедленно останавливается на недопустимом входе, а не бесполезно вращается в состоянии приемника до конца ввода. После минимизации состояние приемника можно удалить.)
С этим соглашением у вашего DFA есть не только принимающие государства;есть одно (неявное) непринятие состояния.Если бы DFA действительно имел только принимающие состояния, то он распознал бы Σ * и мог бы быть действительно сведен к одному принимающему состоянию.
Алгоритм Хопкрофта выполняется за время O (sN log N), где s - это размералфавита и N является числом состояний.Поскольку предполагается, что DFA является полным, sn также является числом ребер в графе автомата (каждое состояние должно иметь s переходов), поэтому мы можем записать это как O (E log N).Но если мы ослабим требование, чтобы DFA был полным, у его графа, вероятно, будет значительно меньше ребер, хотя только с постоянным коэффициентом (если мы примем размер алфавита постоянным).Было несколько предложений алгоритмов, которые пытаются воспользоваться этим фактом.См., Например, Мари-Пьер Беал, Максим Крочемор.Минимизация неполных автоматов.Методы конечных состояний и обработка естественного языка (FSMNLP'08), 2008, США.С. 9-16, 2008, Объединенный исследовательский центр.