dfa - 证明语言是可判定的

Question

我如何显示这种语言

{<C,A,B> | C,A,B are DFAs, L(C) contains the shuffle of L(A) and L(B)} 

是可判定的？

我相信如果我可以为 A 和 B 构建自动机，那么我可以得到一个包含它们的 shuffle 的自动机。

我也在考虑使用空性测试，但我还没有取得任何进展。

Answer 1

1. 给定 DFA A 和 B，构造一个 DFA D 使得 L(D) 等于 L(A) 和 L(B) 的 shuffle。

2. 然后，使用语言 L(M1) = L(C) \ L(D) 和 L(M2) = L(D) \ L(C) 的笛卡尔积机器构造来构造两个 DFA。

3. 如果 L(M1) 和/或 L(M2) 中的任何一个为空，请确定哪个。

   • 如果 L(M1) 为空且 L(M2) 为空，则 L(C) 是 L(A) 和 L(B) 的 shuffle
   • 如果 L(M1) 为空，则 L(C) 是 L(A) 和 L(B) 的 shuffle 的子集
   • 如果 L(M2) 为空，则 L(C) 是 L(A) 和 L(B) 的 shuffle 的超集

要做#1：创建一个新的 DFA，其状态为三元组 (x, y, z)，其中：

1. x 是来自 A 的状态
2. y 是来自 B 的状态
3. z 为 1 或 2

DFA 的初始状态将是 (qi_A, qi_B, 1)。输入字母表将是 A 和 B 的输入字母表的并集。转换将是这样的：

• f((x,y,1), a) = (x',y,2) 其中 f(x,a) = x' 在机器 A 中
• f((x,y,2), b) = (x,y',1) 其中 f(y,b) = y' 在机器 B 中

接受状态应该是在 A 或 B 中接受的状态（或者如果您愿意，也可以只是 B）。

要做#2：创建一个新的 DFA，其状态是对 (x, y) 其中：

1. x 是来自 D 的状态
2. y 是来自 C 的状态

他 DFA 的初始状态将是 (qi_D, qi_C)。输入字母表将是 A 和 C 的输入字母表的并集。转换将是这样的：

• f((x,y),c) = (x',y') 其中 f(x,c) = x' 在 D 中， f(y,c) = y' 在 C 中。

接受状态将是：

• 对于 L(D) \ L(C)，在 D 中接受但不接受 C 的状态
• 对于 L(C) \ L(D)，在 C 中接受但不接受 D 的状态

要做#3：

1. 您可以使用众所周知的 DFA 最小化算法来最小化 DFA。如果您最终得到一个具有单个非接受状态的 DFA，则该语言为空。

2. 您可以尝试所有输入字符串，直到生成的 DFA 的抽水长度（不会导致 DFA 多次进入任何状态的字符串）。如果 DFA 不接受这些，则 DFA 不接受任何字符串并且语言为空。