computer-science - 语言 {⟨A⟩∣A 是 NFA 并且 L(A)={0,1}∗} 是可判定的吗？可判定的？

Question

如何证明/反驳语言 {⟨A⟩∣A 是 NFA 并且 L(A)={0,1}∗} 是/不可判定的？

起初我假设因为它涉及 NFA，所以它是可判定的，但由于没有输入字符串来模拟，这会改变事情吗？如果是这样，怎么做？我想不出能决定这一点的图灵机。由于 {0, 1}* 在理论上是无限的，这是否意味着图灵机可能永远不会停止，因此语言是不可判定的？如果是这样，我该如何证明这一点？

Answer 1

非正式地说，您可以通过构造图灵机来证明这一点，构造一个等效于 NFA A 的 DFA D_A。然后构造接受语言 {0,1}* 的 DFA D_0，然后我们可以模拟 EQ_DFA 上的决策器。

正式地说，构造 TM S: S = "On input :

1. 构造等效于 A 的 DFA D_A
2. 构造接受 {0,1}* 的 DFA D_0
3. 在 EQ_{DFA} = { | 上模拟 EQ_DFA 的判定器 F A 和 B 是 DFA，L(A)=L(B)}（我们知道 EQ_{DFA} 是可判定语言）。
4. 如果 F 接受，则接受；如果 F 拒绝，则拒绝。”

Answer 2

不太正式：

1. 我们可以根据我们的格式通过算法确定检查输入是否代表 NFA
2. 我们可以使用子集构造在算法上构造一个等效于 NFA 的 DFA
3. 我们可以使用几种已知算法中的任何一种在算法上最小化 DFA
4. 我们可以通过算法将得到的 DFA 与 {0, 1}* 的单态 DFA 进行比较
5. 如果相等，则输出是；否则，输出编号。

因为我们可以描述一个算法来做到这一点，并且因为我们不认为我们有比图灵机更多的计算能力（至少上述计算不需要这样），所以问题必须是可判定的。