我正在为我的计算理论课做作业,并且有点困惑如何组合 2 个 DFA。这本书说它使用“交叉结构”来做到这一点,但我不确定那是什么。这里有 2 个例子:
2 回答
这个想法非常简单,尽管我可以看到混淆的地方。我将通过笛卡尔积机器构造(与您所说的相同)对创建交集(联合,差异)机器的过程进行文本/符号描述关于)。
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))。
给你!现在让我们考虑两台机器:一台接受 a^2n,另一台接受 a^3n(交集应该是一台接受 a^6n 的机器......对吗?)。
对于 M',我们有...
- E' = {一个}
- Q' = {s0, s1}
- q0' = s0
- A' = {s0}
- f'(s0, a) = s1, f'(s1, a) = s0
对于 M'',我们有...
- E'' = {一个}
- 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)。
你去吧!请让我知道这是否需要澄清。
它们是: {s∈{a,b,c}∗:s 中的每个 a 都紧跟 ab} {s∈{a,b,c}∗:s 中的每个 a 紧跟 ab} 和 {s ∈{a,b,c}∗: s 中的每个 c 都紧跟在 ab} 之前
在前面和另一个自动机中,您可以加入状态“0”和“2”。
你需要保留那个......
有一种精确的方法可以执行跨语言的自动机。设 AA 和 BB 为输入自动机。新自动机的情况是AA和BB的所有状态对,即SA∩B=SA×SBSA∩B=SA×SB,初始状态为iA∩B=⟨iA,iB⟩iA∩B= ⟨iA,iB⟩,其中 iAiA 和 iBiB 是 AA 和 BB 的初始状态,FA∩B=FA×FBFA∩B=FA×FB 其中 FXFX 表示 XX 的接受状态集合。最后,对于任何字母 α∈Σα∈Σ 和状态 p1,p2∈SAp1,p2∈SA,q1,q2∈SBq1,q2∈SB 定义转换函数 δA∩BδA∩B 如下:
⟨p1,q1⟩−→−−A∩B α ⟨p2,q2⟩ iff p1−→A α p2andq1−→B α q2 ⟨p1,q1⟩→A∩B α ⟨p2,q2⟩ iff p1→A α p2andq1→B α q2 请注意,这种自动机通常不是最小的(例如,交集可能只是一种空语言)。此外,由于输出的大小是二次的,因此使输入自动机最小化可能很有用(但不是必需的)。// 参考:math.stackexchange.com Happy Coding ...