Automata Theory 简明教程

Accepted Language & Decided Language

如果对任何输入字符串 w 都进入最终状态，那么 TM 会接受一种语言。如果图灵机接受一种语言，则该语言是递归可枚举的（由 0 型语法生成）。

如果 TM 接受一种语言并且对语言中不存在的任何输入进入一个拒绝状态，则该 TM 判定一种语言。如果图灵机判定一种语言，则该语言是递归的。

在某些情况下，TM 可能不会停止。此类 TM 会接受该语言，但不会判定它。

Designing a Turing Machine

下面已借助几个示例说明了设计图灵机的基本准则。

Example 1

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

Solution

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

  1. 令 q1 为初始状态。

  2. 如果 M 处于 q1 ；在扫描 α 时，它将进入状态 q2 并写入 B （空格）。

  3. 如果 M 处于 q2 ；在扫描 α 时，它将进入状态 q1 并写入 B （空格）。

  4. 从上述动作中，我们可以看出当扫描到偶数个 α 时， M 会进入状态 q1 ，当扫描到奇数个 α 时，它会进入状态 q2 。因此， q2 是唯一接受的状态。

因此，

M = {{q1, q2}, {1}, {1, B}, δ, q1, B, {q2}}

其中 δ 表示为 −

Tape alphabet symbol

Present State ‘q1’

Present State ‘q2’

α

BRq2

BRq1

Example 2

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

Solution

我们假设输入字符串在字符串的每端都由空格符号 B 终止。

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

  1. 令 q0 为初始状态。

  2. 如果 M 在 q0 中，在读取 0 时，它向右移动，进入状态 q1 并擦除 0。在读取 1 时，它进入状态 q2 并向右移动。

  3. 如果 M 在 q1 中，在读取 0 时，它向右移动并擦除 0，即用 B 替换 0。到达最左端的 1 时，它进入 q2 并向右移动。如果它到达 B，即字符串只包含 0，则它向左移动并进入状态 q3 。

  4. 如果 M 在 q2 中，在读取 0 或 1 时，它向右移动。到达 B 时，它向左移动并进入状态 q4 。这验证了字符串只包含 0 和 1。

  5. 如果 M 在 q3 中，它用 0 替换 B，向左移动并到达最终状态 qf 。

  6. 如果 M 在 q4 中，在读取 0 或 1 时，它向左移动。到达字符串的开头（即读取 B 时），它到达最终状态 qf 。

因此，

M = {{q0, q1, q2, q3, q4, qf}, {0,1, B}, {1, B}, δ, q0, B, {qf}}

其中 δ 表示为 −

Tape alphabet symbol

Present State ‘q0’

Present State ‘q1’

Present State ‘q2’

Present State ‘q3’

Present State ‘q4’

0

BRq1

BRq1

ORq2

-

OLq4

1

1Rq2

1Rq2

1Rq2

-

1Lq4

B

BRq1

BLq3

BLq4

OLqf

BRqf