语言 {⟨A⟩∩A 是 NFA 并且 L(A)={0,1}∗} 是可判定的吗？可决定的？
Is the language {⟨A⟩∣A is an NFA and L(A)={0,1}∗} decidable? decidable?
如何proving/disproving 语言 {⟨A⟩∩A 是一个 NFA 并且 L(A)={0,1}∗}
is/isn不可判定？
一开始我假设因为它是一个 NFA，所以它是可判定的，但是因为没有输入字符串来模拟，这会改变事情吗？如果是这样，如何？我想不出可以决定这一点的图灵机。
由于 {0, 1}* 理论上是无限的是否意味着图灵机可能永远不会停止，因此语言是不可判定的？如果是这样，我该如何证明这一点？
通俗地说，您可以通过构造一个图灵机构造一个 DFA D_A 等同于 NFA A 来证明这一点。然后构造接受语言 {0,1}* 的 DFA D_0 ，然后我们可以在 .
上模拟 EQ_DFA 的决策者
形式上来说，构造TM S：
S = "输入时：
- 构造 DFA D_A 等同于 A
- 构建接受 {0,1}*
的 DFA D_0
- 为 EQ_DFA 模拟决策 F，其中 EQ_{DFA} = { | A 和 B 是 DFA，L(A)=L(B)}（我们知道 EQ_{DFA} 是一种可判定语言）。
- 如果 F 接受，则接受；如果 F 拒绝，则拒绝。"
不太正式：
- 我们可以根据我们的格式通过算法确定检查输入是否表示 NFA
- 我们可以使用子集构造在算法上构造等同于 NFA 的 DFA
- 我们可以使用几种已知算法中的任何一种通过算法最小化 DFA
- 我们可以通过算法将生成的 DFA 与 {0, 1}*
的单态 DFA 进行比较
- 若相等则输出yes；否则，输出编号
因为我们可以描述一个算法来做到这一点，并且因为我们不认为我们有比图灵机更多的计算能力（至少上述计算不需要这样），所以问题必须是可判定的。
如何proving/disproving 语言 {⟨A⟩∩A 是一个 NFA 并且 L(A)={0,1}∗} is/isn不可判定？
一开始我假设因为它是一个 NFA，所以它是可判定的，但是因为没有输入字符串来模拟，这会改变事情吗？如果是这样，如何？我想不出可以决定这一点的图灵机。 由于 {0, 1}* 理论上是无限的是否意味着图灵机可能永远不会停止，因此语言是不可判定的？如果是这样，我该如何证明这一点？
通俗地说，您可以通过构造一个图灵机构造一个 DFA D_A 等同于 NFA A 来证明这一点。然后构造接受语言 {0,1}* 的 DFA D_0 ，然后我们可以在 .
上模拟 EQ_DFA 的决策者形式上来说，构造TM S： S = "输入时：
- 构造 DFA D_A 等同于 A
- 构建接受 {0,1}* 的 DFA D_0
- 为 EQ_DFA 模拟决策 F，其中 EQ_{DFA} = { | A 和 B 是 DFA，L(A)=L(B)}（我们知道 EQ_{DFA} 是一种可判定语言）。
- 如果 F 接受，则接受；如果 F 拒绝，则拒绝。"
不太正式：
- 我们可以根据我们的格式通过算法确定检查输入是否表示 NFA
- 我们可以使用子集构造在算法上构造等同于 NFA 的 DFA
- 我们可以使用几种已知算法中的任何一种通过算法最小化 DFA
- 我们可以通过算法将生成的 DFA 与 {0, 1}* 的单态 DFA 进行比较
- 若相等则输出yes；否则，输出编号
因为我们可以描述一个算法来做到这一点，并且因为我们不认为我们有比图灵机更多的计算能力（至少上述计算不需要这样），所以问题必须是可判定的。