
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- Moore 機與 Mealy 機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的封閉性
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 由 CFG 構造 PDA
- 下推自動機和語法分析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性有界自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
接受的語言和確定的語言
如果圖靈機對任何輸入字串 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 |