finite-automata - 如何使用交集构造形成DFA？

Question

我正在为我的计算理论课做作业，对如何组合 2 个 DFA 有点困惑。这本书说它使用“交叉结构”来做到这一点，但我不确定那是什么。这里有2个例子:

Answer 1

这个想法非常简单，尽管我可以看到混淆的地方。我将通过笛卡尔积机器构造(与您所说的相同关于)。

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 in A' 和 y in A''(对于联合，x in A' 或 y in A''；对于差异，x in A' 但不是 y in A' ')。

取 f'''((x, y), e) = (f'(x, e), f''(y, e))。

你去吧!现在让我们考虑两台机器:一台接受 ^2n，另一台接受 ^3n(交集应该是一台接受 ^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)。

你去吧!如果这需要澄清，请告诉我。