Создание исключающего или из двух детерминированных конечных автоматов (детерминированных конечных машин)

Question

Два DFA (детерминированные конечные автоматы или детерминированные конечные автоматы - которые далее будут называться DFA) Определено по набору DFA 1: L1 = {Q1, E, D1, s1, F} DFA 2: L2 = {Q2, E, D2, s2, F}

Q - список состояний. Пример 1, 2, 3, 4 или а, б, в, д

E - это язык Ex. 0, 1

D - это набор переходов Ex. {(a, 0, b)} состояние a переходит к b на 0

s - это начальное состояние

F - конечное состояние

Как бы вы взяли и эксклюзив - или два DFA L1 и L2

Answer 1

Q = Q1 X Q2;

E = E;

D - все переходы, которые согласуются из обеих систем;

s = S1 пересекаются S2;

F = F1 XOR F2

Answer 2

Вот несколько общих советов, с которых можно начать ...

Возможно, вы захотите создать еще один DFA, состояния Q3 которого идентифицируются с элементами декартового произведения Q1 и Q2.Из s1 и s2 должно быть довольно очевидно, какой элемент Q3 должен быть обозначен как начальное состояние.
Тогда, учитывая любой узел (n1 в Q1, n2 в Q2) в Q3, должно быть довольно легко выяснитьгде края должны идти для каждого входа.И F3 будет набором состояний (n1, n2), где (n1 в F1 XOR n2 в F2) выполняется.