1

两个 DFA(Deterministic Finite Automaton 或 Deterministic Fininte-State Machines - 从这里开始称为 DFA)在集合 DFA 1 上定义:L1 = {Q1,E,D1,s1,F} DFA 2:L2 = {Q2, E, D2, s2, F}

Q 是状态列表。例如 1、2、3、4 或 a、b、c、d

E是语言Ex。0, 1

D 是转移集 Ex。{(a,0,b)} 状态 a 在 a 0 上进入 b

s 是起始状态

F是最终状态

您将如何取两个 DFA L1 和 L2 的异或

4

2 回答 2

0

这里有一些广泛的提示可以帮助您入门...

您可能想要构建另一个 DFA,其状态 Q3 由 Q1 和 Q2 的笛卡尔积的元素标识。从 s1 和 s2 来看,应该很明显应该将 Q3 的哪个元素指定为起始状态。
然后,给定 Q3 中的任何节点(Q1 中的 n1,Q2 中的 n2),应该很容易找出每个输入的边需要去哪里。F3 将是一组状态 (n1, n2),其中 (n1 in F1 XOR n2 in F2) 成立。

于 2010-10-06T00:11:42.550 回答
-1

Q = Q1 X Q2;

E = E;

D 是两个系统一致的所有转换;

s = S1 与 S2 相交;

F = F1 异或 F2

于 2010-10-06T00:39:11.720 回答