6

我不明白为什么图灵机 T，在没有标记接受状态时接受并在标记接受状态时拒绝：

E(dfa) = {| A 是 DFA 并且 L(A) = 空集（没有符号）}

E(dfa) 是一种可判定语言。

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

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

这对我来说似乎倒退了。谁能解释一下？

谢谢你。

4

1 回答 1

8

我相信您的困惑是由于在不同的上下文中使用了“接受”和“拒绝”这两个词。在高层次上，很容易避免这种混淆，因为您可以将图灵机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( A ) 为空，则 L( T ) 接受A。

现在你的证明更详细地说明了T如何决定是否接受A，但我认为你的困惑更多地围绕着接受和拒绝的多种用途。很宽泛地说，当A拒绝一切时，你可以说T接受A。

于 2014-03-07T23:04:55.677 回答