Как построить объединение двух DFA?

Есть ли у кого-нибудь прямое описание алгоритма построения объединения двух данных 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, или мне что-то не хватает?

8
задан Old McStopher 15 December 2010 в 12:39
поделиться