Алгоритмы минимизации автоматов Мура

Алгоритм Бжозовского можно распространить на автоматы Мура, но его временная сложность в целом экспоненциальна. Есть ли другой алгоритм минимизации автоматов Мура? Какое время работы этих алгоритмов, если таковые имеются?

Оригинальный алгоритм минимизации DFA был фактически разработан для машин Мура , руководствуясь их явно более наблюдаемым поведением. Но алгоритм, представленный здесь, является реконструкцией из минимизации DFA, так как я обнаружил историческое свидетельство после факта.

После Википедии (с некоторыми нотационными изменениями):

Мур машина может быть определена как 6-кортеж , состоящая из следующих действий :$(Q, q_0, \Sigma, \Pi, \delta, \gamma)$

• конечный набор состояний$Q$
• начальное состояние (также называемое начальным состоянием) которое является элементом$q_0$$Q$
• конечный набор, называемый входным алфавитом$\Sigma$
• конечный набор, называемый выходным алфавитом$\Lambda$
• функция перехода отображающая состояние и входной алфавит в следующее состояние $\delta : Q \times \Sigma \rightarrow Q$
• выходная функция отображающая каждое состояние в выходной алфавит $\gamma : Q \rightarrow \Pi$

Согласно этому определению, машина Мура является детерминированным датчиком конечных состояний.

У меня нет ссылки на минимизацию автоматов Мура. Однако кажется не слишком сложным представить алгоритм, полученный из алгоритма, используемого для детерминированных автоматов в конечных состояниях.

Идея минимизации DFA основана на характеристике Myhill-Nerode обычных языков .

С учетом языком , и пару строк и , определяет отличительное расширение быть строкой таково , что именно один из двух строк и принадлежит . Определите отношение для строк по правилу, что если нет различающего расширения для и . Легко показать, что является отношением эквивалентности на строках, и, таким образом, оно делит множество всех строк на классы эквивалентности.x y z x z y z L R L x R L y x y R $L$$x$$y$$z$$xz$$yz$$L$$R_L$$x R_L y$$x$$y$$R_L$

Теорема Майхилла-Нерода утверждает, что является регулярной тогда и только тогда, когда имеет конечное число классов эквивалентности, и, кроме того, что число состояний в наименьшем детерминированном конечном автомате (DFA), распознающих , равно числу классов эквивалентности в .R L L R $L$$R_L$$L$$R_L$

Действительно, каждое состояние наименьшего DFA таково, что как определено выше, является одним из классов эквивалентности для отношения .W q R $q$$W_q$$R_L$

Для DFA для обычного языка легко показать, что каждый набор содержит строки, которые принадлежат одному и тому же эквивалентному классу относительно .W q R $L$$W_q$$R_L$

Следовательно, минимизация DFA фактически состоит из состояний слияния (рассматриваемых как наборы эквивалентных строк), всякий раз, когда показано, что два различных состояния содержат эквивалентные строки.

Для этой цели существуют два достаточно быстрых алгоритма: алгоритм Мура (1956), который находится во времени и алгоритм Хопкрофта (1971) во время O ( n log n ) .$O(n^2)$$O(n\log n)$

Расширение автоматов Мура лучше всего можно понять в переопределении отношения эквивалентности в качестве для преобразователя . Отношение было связано с тем, приведет ли будущий ввод к эквивалентному состоянию принятия. отношение эквивалентности автоматов Мура касается , будет ли вход в будущем производить тот же результат. T R L R $R_T$$T$$R_L$$R_T$

Следовательно, для преобразователя и двух строк и мы определяем отличительное расширение как строку такую ​​что и с , то есть такой, что выходное поведение преобразователя для различается в зависимости от того, следует ли он за или .x y z T ( x z ) = T ( x ) u T ( y z ) = T $T$$x$$y$$z$$T(xz)=T(x)u$u ≠ v z x $T(yz)=T(y)v$$u\neq v$$z$$x$$y$

Опять же, является отношением эквивалентности, разделяющим все строки в на классы эквивалентности. В случае машины Мура эти классы снова будут соответствовать состоянию минимального преобразователя.Σ $R_T$$\Sigma^*$

Следующий алгоритм имитирует алгоритм Мура для минимизации DFA.

Мы определим начальное разбиение из на классы состояний следующим образом: Q S $\mathcal P$$Q$$S_e$

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Затем мы разбиваем классы в следующим образом:$\mathcal P$

повторять последовательно для каждого класса состояний , пока ничего не изменится repeat Если то ничего не делать еще Раскол в подмножества такие , что для каждого подмножества , существует другой класс такая что (подмножества заменяют в$S$
$\ \ $ $\forall a\in\Sigma,\;$
$\ \ \ \ $ S S i S $\exists S'\in \mathcal P,\; \forall q\in S,\; \delta(q,a)\in S'$
$\ \ \ \ $ $S$$S_i$
$\ \ \ \ \ \ $$S_i$ ∀ q ∈ S i$S'\in \mathcal P$$\forall q\in S_i,\; \delta(q,a)\in S'$
$\ \ \ \ \ \ $ S $S_i$$S$$\mathcal P$)

Когда не осталось ни одного класса, который нужно разделить, оставшиеся классы состояний сформируют состояния минимальной машины Мура.

По построению все состояния в классе имеют одинаковый вывод, который является выходом для класса.

Аналогично, для любого входа все состояния в классе переходят в некое состояние в том же другом классе, который определяет функцию перехода для минимальной машины Мура.$a\in\Sigma$

Анализ сложности: Пустьбыть числом состояний, иразмер входного алфавита. Основной цикл выполняется не более раз, поскольку каждая итерация должна разбивать как минимум один класс состояний, а каждый класс содержит как минимум одно состояние. Каждая итерация цикла проверяет каждое состояние конечное число раз и пропорционально количеству входных символов. Следовательно, сложность алгоритма , такая же, как и у алгоритма минимизации DFA, который послужил ориентиром для этого.s = | Σ | n O ( s n 2$n=|Q|$$s=|\Sigma|$
$n$$O(sn^2)$

У меня нет никаких ссылок на эту минимизацию машин Мура. Возможно, это включено в его статью:

Мур, Эдвард Ф. (1956). «Геданкен-эксперименты на последовательных машинах». Исследования автоматов , Анналы математических исследований (Принстон, Нью-Джерси: издательство Принстонского университета) (34): 129-153.

Эта статья является основным справочником, представляющим машины Мура . Это также ссылка на алгоритм минимизации DFA Мура . Таким образом, должно быть удивительно, если бы адаптация алгоритма к минимизации машин Мура не была, по крайней мере, предложена в этой статье. Я проверил статью, и представленная версия алгоритма минимизации на самом деле предназначена для машин Мура, а не для DFA. Бумага хорошо написана, но стиль того времени делает ее немного труднее читать. Интересно заметить, что многие из идей теории конечных автоматов Майкла-Нерода уже изложены в этой статье.

Более свежий алгоритм Джона Хопкрофта (1971) должен быть аналогичным образом адаптирован к машинам Мура. Не ясно, было ли какое-либо основание публиковать эту адаптацию где-либо, и статья Хопкрофта, похоже, не имеет никакого отношения к машинам Мура.$O(sn\log n)$

Вариант алгоритма Бжозовского, использующий производные регулярных выражений, приведен в [2], глава 12, раздел 4, где он зачислен в [4]. См. [1] и [3] для более общего случая субпоследовательных преобразователей (терминология немного устарела, и термин « последовательный преобразователь» , вероятно, более уместен в настоящее время).

[1] К. Чоффрут, Минимизация субпоследовательных преобразователей: обзор, Теорема. Комп. Sci. 292 (2003), 131–143.

[2] С. Эйленберг, Автоматы, Языки и машины, вып. A, Academic Press, 1974.

[3] Ж.-Е. Pin, учебник по последовательным функциям . (Слайды)

[4] Г. Н. Рене, Последовательные функции, JACM 5 (1958), 177–180.

Алгоритм Бжозовского - плохая отправная точка (если вас интересует асимптотическое время выполнения в худшем случае). Даже Википедия говорит вам так:

Как заметил Бжозовский (1963), обращение ребер DFA создает недетерминированный конечный автомат (NFA) для обращения исходного языка и преобразования этого NFA в DFA с использованием стандартной конструкции powerset (построение только достижимых состояний преобразованный DFA) приводит к минимальному DFA для того же самого обращенного языка. Повторение этой операции обращения во второй раз приводит к минимальному DFA для исходного языка. Сложность алгоритма Бжозовского в наихудшем случае является экспоненциальной, поскольку существуют обычные языки, для которых минимальное DFA обращения существенно экспоненциально больше минимального DFA языка [6], но оно часто работает лучше, чем можно предположить в этом худшем случае.

Алгоритм имеет экспоненциальное время выполнения в худшем случае даже на DFA, потому что он вычисляет автомат для обратного, который может быть экспоненциально большим. Так что ваша проблема не в расширении до преобразователей.

Попробуйте адаптировать другой алгоритм минимизации DFA.