Минимизируйте DFA с безразличными переходами

Я думаю, что эта задача является NP-сложной (подробнее об этом чуть позже). Это то, что я бы попробовал.

1. (Необязательно) Предварительно обработайте ввод с помощью обычного алгоритма минимизации с принятием/отклонением/безразличием в качестве отдельных результатов. (Поскольку все равно не эквивалентно принятию или отклонению, мы получаем обратно отношение эквивалентности Майхилла-Нероде, допуская вариант обычного алгоритма.)

2. Создайте граф конфликта следующим образом. Начните со всех ребер между принимающим и отвергающим состояниями. Возьмем замыкание, в котором мы итеративно добавляем ребра q₁ — q₂ так, что существует символ s, для которого существует ребро (q₁ , с) — (q₂, с).

3. Раскрасьте этот график как можно меньшим количеством цветов. (Или приблизительно.) Существует множество алгоритмов раскраски. PartialCol — хорошая отправная точка.

4. Объедините каждый цветовой класс в один узел. Это потенциально делает новую функцию перехода многозначной, но мы можем выбирать произвольно.

Имея доступ к алфавиту произвольного размера, кажется достаточно простым заставить это сведение к раскраске работать в обратном направлении, доказывая NP-трудность. Для меня открытый вопрос заключается в том, ограничивает ли наличие алфавита фиксированного размера граф конфликтов таким образом, чтобы как-то упростить результирующий экземпляр раскраски. Увы, у меня нет времени исследовать это.

Я считаю, что небольшая вариация обычного алгоритма Мура работает. Вот формулировка алгоритма.

Let S be the set of states.
Let P be the set of all unordered pairs drawn from S.
Let M be a subset of P of "marked" pairs.
Initially set M to all pairs where one state is accepting and the other isn't. 
Let T(x, c) be the transition function from state x on character c.
Do
  For each pair z = <a, b> in P - M
    For each character c in the alphabet
      If <T(a, c), T(b, c)> is in M
        Add z to M and continue with the next z
Until no new additions to M

Окончательное множество P — M представляет собой попарное описание отношения эквивалентности состояний. Из него вы можете создать минимальный DFA, объединив состояния и переходы оригинала.

Я считаю, что безразличные переходы можно обрабатывать, никогда не отмечая (добавляя к M) пары на их основе. То есть меняем одну строчку:

      If T(a, c) != DC and T(b, c) != DC and <T(a, c), T(b, c)> is in M   

(На самом деле в реализации никаких реальных изменений алгоритма не требуется, если DC является зарезервированным значением состояния типа, которое не является состоянием в исходном FA.)

У меня сейчас нет времени думать о формальном доказательстве, но мне это интуитивно понятно. Мы пропускаем разделение классов эквивалентности состояний на основе переходов, которые, как мы знаем, никогда не произойдут.

Мне все еще нужно доказать себе, является ли множество Р — М попарным описанием отношения эквивалентности. То есть можем ли мы получить <a,b> и <b,c>, но не <a,c>? Если да, то есть ли исправление?