接受的語言和確定的語言



如果圖靈機對任何輸入字串 w 進入最終狀態,則它接受該語言。如果圖靈機接受一種語言,則該語言是可列舉遞迴的(由 0 型文法生成)。

如果圖靈機接受一種語言並且對語言中不存在的任何輸入進入拒絕狀態,則它判定該語言。如果圖靈機判定一種語言,則該語言是遞迴的。

在某些情況下,圖靈機可能不會停止。這樣的圖靈機接受該語言,但它並不判定它。

圖靈機設計

下面將通過幾個例子解釋圖靈機設計的基本指導原則。

示例 1

設計一個圖靈機來識別所有包含奇數個 α 的字串。

解決方案

圖靈機 **M** 可以透過以下步驟構建:

  • 設 **q1** 為初始狀態。

  • 如果 **M** 處於 **q1** 狀態;掃描到 α 時,它進入 **q2** 狀態並寫入 **B**(空格)。

  • 如果 **M** 處於 **q2** 狀態;掃描到 α 時,它進入 **q1** 狀態並寫入 **B**(空格)。

  • 從上述步驟可以看出,如果 **M** 掃描到偶數個 α,它將進入 **q1** 狀態;如果它掃描到奇數個 α,它將進入 **q2** 狀態。因此,**q2** 是唯一的接受狀態。

因此,

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

其中 δ 由下式給出:

磁帶字母符號 當前狀態 ‘q1 當前狀態 ‘q2
α BRq2 BRq1

示例 2

設計一個圖靈機,讀取表示二進位制數的字串,並擦除字串中所有前導的 0。但是,如果字串只包含 0,則保留一個 0。

解決方案

讓我們假設輸入字串在字串的每一端都以空格符號 B 結尾。

圖靈機 **M** 可以透過以下步驟構建:

  • 設 **q0** 為初始狀態。

  • 如果 **M** 處於 **q0** 狀態,讀取 0 時,它向右移動,進入 **q1** 狀態並擦除 0。讀取 1 時,它進入 **q2** 狀態並向右移動。

  • 如果 **M** 處於 **q1** 狀態,讀取 0 時,它向右移動並擦除 0,即用 B 代替 0。到達最左邊的 1 時,它進入 **q2** 狀態並向右移動。如果它到達 B,即字串只包含 0,則它向左移動並進入 **q3** 狀態。

  • 如果 **M** 處於 **q2** 狀態,讀取 0 或 1 時,它向右移動。到達 B 時,它向左移動並進入 **q4** 狀態。這驗證了字串只包含 0 和 1。

  • 如果 **M** 處於 **q3** 狀態,它將 B 替換為 0,向左移動併到達最終狀態 **qf**。

  • 如果 **M** 處於 **q4** 狀態,讀取 0 或 1 時,它向左移動。到達字串的開頭,即讀取 B 時,它到達最終狀態 **qf**。

因此,

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

其中 δ 由下式給出:

磁帶字母符號 當前狀態 ‘q0 當前狀態 ‘q1 當前狀態 ‘q2 當前狀態 ‘q3 當前狀態 ‘q4
0 BRq1 BRq1 0Rq1 - 0Lq1
1 1Rq2 1Rq2 1Rq2 - 1Lq4
B BRq1 BLq3 BLqf 0Lqf BRqf
廣告