Automata Theory 简明教程

Accepted Language & Decided Language

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

A TM accepts a language if it enters into a final state for any input string w. A language is recursively enumerable (generated by Type-0 grammar) if it is accepted by a Turing machine.

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

A TM decides a language if it accepts it and enters into a rejecting state for any input not in the language. A language is recursive if it is decided by a Turing machine.

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

There may be some cases where a TM does not stop. Such TM accepts the language, but it does not decide it.

Designing a Turing Machine

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

The basic guidelines of designing a Turing machine have been explained below with the help of a couple of examples.

Example 1

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

Design a TM to recognize all strings consisting of an odd number of α’s.

Solution

Solution

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

The Turing machine M can be constructed by the following moves −

  1. Let q1 be the initial state.

  2. If M is in q1; on scanning α, it enters the state q2 and writes B (blank).

  3. If M is in q2; on scanning α, it enters the state q1 and writes B (blank).

  4. From the above moves, we can see that M enters the state q1 if it scans an even number of α’s, and it enters the state q2 if it scans an odd number of α’s. Hence q2 is the only accepting state.

因此，

Hence,

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

其中 δ 表示为 −

where δ is given by −

Tape alphabet symbol

Present State ‘q1’

Present State ‘q2’

α

BRq2

BRq1

Example 2

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

Design a Turing Machine that reads a string representing a binary number and erases all leading 0’s in the string. However, if the string comprises of only 0’s, it keeps one 0.

Solution

Solution

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

Let us assume that the input string is terminated by a blank symbol, B, at each end of the string.

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

The Turing Machine, M, can be constructed by the following moves −

  1. Let q0 be the initial state.

  2. If M is in q0, on reading 0, it moves right, enters the state q1 and erases 0. On reading 1, it enters the state q2 and moves right.

  3. If M is in q1, on reading 0, it moves right and erases 0, i.e., it replaces 0’s by B’s. On reaching the leftmost 1, it enters q2 and moves right. If it reaches B, i.e., the string comprises of only 0’s, it moves left and enters the state q3.

  4. If M is in q2, on reading either 0 or 1, it moves right. On reaching B, it moves left and enters the state q4. This validates that the string comprises only of 0’s and 1’s.

  5. If M is in q3, it replaces B by 0, moves left and reaches the final state qf.

  6. If M is in q4, on reading either 0 or 1, it moves left. On reaching the beginning of the string, i.e., when it reads B, it reaches the final state qf.

因此，

Hence,

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

其中 δ 表示为 −

where δ is given by −

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