表明语言是可判定的

Question

如何显示此语言

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

是可判定的吗？

我相信如果我能为 A 和 B 构造自动机，那么我就能得到一个包含它们洗牌的自动机。

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

Answer 1

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

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

3. 如果L(M1)and/orL(M2)中任一个为空，则判断哪个

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

要做 #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) 其中机器 B 中的 f(y,b) = y'

接受状态应为 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') 其中，D 中的 f(x,c) = x'，C 中的 f(y,c) = y'。

接受状态为：

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

要做#3：

1. 您可以使用众所周知的 DFA 最小化算法来最小化 DFA。如果你最终得到一个只有一个非接受状态的 DFA，那么语言就是空的。

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