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