为什么E（dfa）是可决定的语言？

Question

我不明白为什么没有标记接受状态时Turing Machine T，ACCEPTS并在标记接受状态时为什么拒绝：

E（dfa）= {| A是DFA，L（A）=空集（没有符号）}

E（dfa）是一种可决定的语言。

证明：DFA可以接受一些字符串，当从起始状态到达接受状态时，可以通过>沿DFA的箭头进行移动来实现。为了测试这种情况，我们可以设计一个> TM T，它使用类似于示例3.23的标记算法。

T =“在input上，其中A为DFA：1.标记A的开始状态。2.重复直到未标记任何新状态：3.标记从已标记的任何状态进入转换的任何状态4.如果没有标记接受状态，则接受；否则，拒绝。”

在我看来，这是倒退的。谁能解释一下？

谢谢。

Answer 1

我相信您的困惑是由于在不同的上下文中使用了“接受”和“拒绝”两个词。从高层次上讲，很容易避免这种混乱，因为您可以定义图灵机T而不引用DFA A自己接受和拒绝的过程。

L（T）为{A | L（A）为空}。这与您的问题中定义的E（dfa）相同，但是使用L（T）使我们在这里处理两种独立的语言更加明确，一种语言恰好是用另一种语言定义的。

如果我们从高层到低层工作，我们可以说：

• 只要L（A）为空，L（T）就接受A。
• 但是，我们如何确定L（A）是否为空？当A拒绝所有字符串时，L（A）为空。
• 我们如何知道A中拒绝了一个字符串？它不会以接受状态结束。

我们现在也可以轻松地从低到高工作：

• 如果提供给A的字符串未以接受状态结束，则将其拒绝。
• 如果所有字符串都被A拒绝，则L（A）为空。
• 如果L（甲）是空的，则L（Ť）接受阿。

现在，您的证明会更详细地说明T如何决定是否接受A，但是我认为您的困惑更多地围绕接受和拒绝的多种用法。非常广泛，可以说牛逼接受一个当且仅当一个废品的一切。