language-agnostic - 为什么 E(dfa) 是一种可判定语言？

Question

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

E(dfa) = {| A is a DFA and L(A) = the empty set(don't have the symbol)}

E(dfa) is a decidable language.

Proof: A DFA accepts some string iff reaching an accept state from the start state by >traveling along the arrows of the DFA is possible. To test this condition, we can design a >TM T that uses a marking algorithm similar to that used in Example 3.23.

T= "On input , where A is a DFA: 1. Mark the start state of A. 2. Repeat until no new states get marked: 3. Mark any state that has a transition coming into it from any state that is already marked. 4. If no accept state is marked, accept; otherwise, reject."

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

谢谢你。

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(A) 为空，则 L(T) 接受 A。

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