Как вы строите союз двух ДФА? - PullRequest
Новая
       8

Как вы строите союз двух ДФА?

8 голосов
/ 15 декабря 2010

Есть ли у кого-нибудь прямое описание алгоритма построения объединения двух данных DFA? Например, скажем, у нас есть два DFA более {0,1}, где 

{w|w has an odd number of characters}
  w has states A and B

delta | 0  | 1
----------------
  A   | B  | B
----------------
  B   | A  | A


{x|x has an even number of 1s}
  x has states a and b

delta | 0  | 1
----------------
  a   | a  | b
----------------
  b   | b  | a

У меня есть итоговая таблица переходов, в которой объединение выглядит так: 

delta | 0  | 1 
----------------
  Aa  | Ba | Bb
----------------
  Ab  | Bb | Ba
----------------
  Ba  | Aa | Ab
----------------
  Bb  | Ab | Aa

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

1 Ответ

9 голосов
/ 15 декабря 2010

Ключ к пониманию заключается в том, что вы должны запускать два DFA одновременно, или в целом вы должны поддерживать состояния обоих DFA в объединенном DFA.

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

Правила перехода для нового DFA могут быть рассчитаны напрямую.Например, если вы находитесь в состоянии Ab и получаете на входе 0, первый DFA перейдет в состояние B, а второй в состояние b, поэтому следующим состоянием DFA объединения для этого входа будет Bb.

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

...