接受的语言和决定的语言

---

如果 TM 进入任何输入字符串 w 的最终状态，则它接受一种语言。如果一种语言被图灵机接受，它就是递归可枚举的（由 Type-0 语法生成）。

如果 TM 接受语言，则决定一种语言，并对任何非该语言的输入进入拒绝状态。如果一种语言是由图灵机决定的，那么它就是递归的。

在某些情况下，TM 可能不会停止。这样的 TM 接受该语言，但并不决定它。

设计图灵机

下面通过几个例子解释了设计图灵机的基本准则。

实施例1

设计一个 TM 来识别所有由奇数个 α 组成的字符串。

解决方案

图灵机M可以通过以下动作构建 -

• 设q ₁为初始状态。

• 如果M在q ₁中；当扫描 α 时，它进入状态q ₂并写入B（空白）。

• 如果M在q ₂中；扫描α时，它进入状态q ₁并写入B（空白）。

• 从上面的动作可以看出，如果M扫描到偶数个α，则进入状态q ₁ ，如果扫描到奇数个α，则进入状态q _{2 。}因此q ₂是唯一的接受状态。

因此，

M = {{q ₁ , q ₂ }, {1}, {1, B}, δ, q ₁ , B, {q ₂ }}

其中 δ 由下式给出 -

实施例2

设计一个图灵机，读取表示二进制数的字符串并删除字符串中所有前导 0。但是，如果字符串仅包含 0，则它会保留一个 0。

解决方案

让我们假设输入字符串在字符串的每一端都以空白符号 B 终止。

图灵机M可以通过以下动作构建 -

• 设q ₀为初始状态。

• 如果M在q ₀中，则在读取0时，它向右移动，进入状态q ₁并擦除0。在读取1时，它进入状态q ₂并向右移动。

• 如果M在q ₁中，则在读取0时，它向右移动并擦除0，即，它用B替换0。到达最左边的 1 后，它进入q ₂并向右移动。如果它到达B，即字符串仅由0组成，则它向左移动并进入状态q ₃。

• 如果M在q ₂中，则在读取 0 或 1 时，它会向右移动。到达 B 后，它向左移动并进入状态q ₄。这验证了该字符串仅包含 0 和 1。

• 如果M在q ₃中，则它用 0 替换 B，向左移动并到达最终状态q _f。

• 如果M在q ₄中，则在读取 0 或 1 时，它会向左移动。当到达字符串的开头时，即当它读取 B 时，它到达最终状态q _f。

因此，

M = {{q ₀ , q ₁ , q ₂ , q ₃ , q ₄ , q _f }, {0,1, B}, {1, B}, δ, q ₀ , B, {q _f }}

其中 δ 由下式给出 -