语言{⟨A⟩⟩A是NFA和L(A)={0,1}∗}可判定吗？可判定的？

Question

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

我最初认为，因为它涉及到NFA，所以它是可判定的，但是由于没有输入字符串来模拟这种变化吗？如果是这样的话，是怎么做的？我想不出有一台图灵机器能决定这一切。由于{0，1}*理论上是无限的，是否意味着图灵机永远不会停止，因此语言是不可判定的？如果是这样的话，我该如何证明呢？

Answer 1

非正式地讲，您可以通过构造一个与NFA等价的图灵机构造一个DFA D_A来展示这一点。然后构造接受语言{0,1}*的DFA D_0，然后我们可以模拟EQ_DFA on的决定器。

从形式上讲，在输入上构造TM S: S=“：

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

Answer 2

较不正式：

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

因为我们可以描述一种算法来做到这一点，而且由于我们不认为我们比图灵机器有更大的计算能力(至少上面的计算不需要这样做)，所以这个问题必须是可判定的。