Как преобразовать два пересекающихся DFA в минимальный DFA

У меня есть следующая проблема: есть два детерминированных конечных автомата, которые должны быть пересечены и преобразованы в один минимальный детерминированный конечный автомат. Есть ли алгоритм для этого?

два DFA

Я знаю, что могу создать NFA, создав декартово произведение двух автоматов и преобразовав результат в DFA, но это процедура, требующая много времени. Есть ли более простой способ создать пересечение двух автоматов?

Кстати: вот решение: Solution

Я попробовал свой подход, как я описал ниже, но я не могу представить, как получить решение: вычисление дополнения двух DFA дает два моих новых DFA ровно с двумя принимающими состояниями. Теперь я должен их объединить и минимизировать, но откуда мне взять третье принимающее состояние?


intersection dfa deterministic automaton
person jannnik    schedule 03.03.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Насколько мне известно, не существует «прямого» алгоритма, который бы это делал. Вы можете сделать это,

  • минимизация двух входных DFA,
  • вычисляя их декартово произведение (которое, кстати, производит еще один DFA, а не NFA), затем
  • минимизация результата.

Нет строгой необходимости минимизировать два входных DFA, но это может повысить эффективность. Если у вас есть DFA с n-состоянием и m-состоянием, их декартово произведение будет иметь состояния O(mn). Алгоритм минимизации DFA выполняется за время O(k2), где k — количество состояний в DFA, поэтому, если исходные DFA имеют размеры n и m, вычисление декартова произведения и последующая минимизация будут занимает время O(m2n2), тогда как минимизация, затем вычисление декартова произведения, а затем снова минимизация занимает время O(m2 + n2 + m'2n'2), где m' и n' — размеры минимизированных DFA.

Надеюсь это поможет!

person templatetypedef    schedule 03.03.2015
comment
Спасибо за ваши идеи! Мне приходится решать такие упражнения вручную, а это значит, что вычисление декартова произведения с O(3²) занимает слишком много времени. Тем временем я нашел способ избежать пересечения DFA, отменив запись ДеМоргана. Мне нужно вычислить дополнение двух DFA и объединить их. Следовательно, шаги будут следующими: (минимизировать входные DFA) - вычислить их дополнения - объединить их - минимизировать результат. Возможен ли этот способ или я что-то пропустил? - person jannnik; 05.03.2015