我正在为我的计算课理论做作业，但对如何合并两个DFA有点困惑。该书说它使用“交叉口构造”来做到这一点，但是我不确定那是什么。这里有两个例子:
这个想法非常简单，尽管我可以看到困惑的根源。我将通过笛卡尔乘积机器结构(与您所说的相同)给出文本/符号描述相交(联合，差异)机器的制造过程。关于)。
DFA是5元组(E，Q，q0，A，f)，其中
E是输入字母，是一组非空的有限符号 Q是状态集，非空和有限 q0是开始状态，是Q 的元素 A是接受状态或最终状态的集合，是Q 的子集 f是转换函数，从Q x E到Q 对
假设我们有两台机器M'=(E'，Q'，q0'，A'，f')和M''=(E''，Q''，q0''，A''，f'') 。为了使讨论更加容易，我们假设E'= E''。现在，我们将构造M'''，以便L(M''')= L(M')相交(或并集或差)L(M'')。
以E'''= E''= E'取Q'''= Q'x Q''取q0'''=(q0'，q0'')取A'''=(x，y)其中x在A'中且y在A''中(对于并集，x在A'中或y在A''中;对于差异，x在A'中而不是在a中”)。 取f'''(((x，y)，e)=(f'(x，e)，f''(y，e))。
你去!现在让我们考虑两台机器:一台接受a ^ 2n，另一台接受a ^ 3n(交集应该是一台接受a ^ 6n ...的机器...对吗？)。
对于M'，我们有...
E'= {a} Q'= {s0，s1} q0'= s0 A'= {s0} f'(s0，a)= s1，f'(s1，a)= s0
对于M''，我们有...
E''= {a} Q''= {t0，t1，t2} q0''= t0 A''= {t0} f''(t0，a)= t1，f''(t1，a)= t2，f''(t2，a)= t0
对于M'''，我们得到...
E'''= {a} Q'''= {(s0，t0)，(s0，t1)，(s0，t2)，(s1，t0)，(s1，t1)，(s1，t2)} q0'''=(s0，t0) A'''= {(s0，t0)}表示交集，{(s0，t0)，(s0，t1)，(s0，t2)，(s1，t0)}表示联合，{(s0，t1) ，(s0，t2)}。 f'''(((s0，t0)，a)=(s1，t1)，f'''((s1，t1)，a)=(s0，t2)，f'''((s0，t2 )，a)=(s1，t0)，f'''((s1，t0)，a)=(s0，t1)，f'''((s0，t1)，a)=(s1，t2) ，f'''(((s1，t2)，a)=(s0，t0)。
然后你去!请让我知道是否需要澄清。