Минимизируйте DFA с помощью безразличных переходов - PullRequest
Новая
       21

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

7 голосов
/ 03 июля 2019

У меня есть DFA ( Q , Σ, δ , q 0 , F ) снекоторые «не заботятся о переходах». Эти переходы моделируют символы, которые, как известно, не появляются на входе в некоторых ситуациях.Если выполняется какой-либо такой переход, не имеет значения, принята полученная строка или нет.

Существует ли алгоритм для вычисления эквивалентного DFA с минимальным количеством состояний?Нормальные алгоритмы минимизации DFA не могут быть использованы, поскольку они не знают о переходах «все равно» и, как представляется, не существует очевидного способа расширения алгоритмов.

Ответы [ 2 ]

4 голосов
/ 06 июля 2019

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

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

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

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

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

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

1 голос
/ 04 июля 2019

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

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.)

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

Что мне еще нужно доказать, так это то, является ли множество P - M попарно описанием отношения эквивалентности. Т.е. можем ли мы в итоге получить <a,b> и <b,c>, но не <a,c>? Если так, есть ли исправление?

...