30

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

在此处输入图像描述

在此处输入图像描述

4

2 回答 2

52

这个想法非常简单，尽管我可以看到混淆的地方。我将通过笛卡尔积机器构造（与您所说的相同）对创建交集（联合，差异）机器的过程进行文本/符号描述关于）。

DFA 是一个 5 元组 (E, Q, q0, A, f)，其中

  1. E 是输入字母表，一个非空的有限符号集
  2. Q 是状态集，非空且有限
  3. q0 是起始状态，Q 的一个元素
  4. A 是接受或最终状态的集合，是 Q 的子集
  5. 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'') 相交（或并集或差集）。

  1. 取 E''' = E'' = E'
  2. 取 Q''' = Q' x Q''
  3. 取 q0''' = (q0', q0'')
  4. 取 A''' = (x, y) 其中 x in A' 和 y in A'' （对于联合，x in A' 或 y in A''；对于差异，x in A' 但不是 y in A' '）。
  5. 取 f'''((x, y), e) = (f'(x, e), f''(y, e))。

给你！现在让我们考虑两台机器：一台接受 a^2n，另一台接受 a^3n（交集应该是一台接受 a^6n 的机器......对吗？）。

对于 M'，我们有...

  1. E' = {一个}
  2. Q' = {s0, s1}
  3. q0' = s0
  4. A' = {s0}
  5. f'(s0, a) = s1, f'(s1, a) = s0

对于 M''，我们有...

  1. E'' = {一个}
  2. Q'' = {t0, t1, t2}
  3. q0'' = t0
  4. A'' = {t0}
  5. f''(t0, a) = t1, f''(t1, a) = t2, f''(t2, a) = t0

对于 M'''，我们得到...

  1. E''' = {a}
  2. Q''' = {(s0, t0), (s0, t1), (s0, t2), (s1, t0), (s1, t1), (s1, t2)}
  3. q0''' = (s0, t0)
  4. A''' = {(s0, t0)} 表示交集，{(s0, t0), (s0, t1), (s0, t2), (s1, t0)} 表示并集，{(s0, t1), (s0, t2)} 差异。
  5. 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)。

你去吧！请让我知道这是否需要澄清。

于 2011-10-17T19:51:03.780 回答
1

它们是： {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 ...

于 2017-12-09T12:54:50.223 回答