
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- 穆爾機與米利機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的閉包特性
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 從 CFG 構造 PDA
- 下推自動機和語法分析
- 圖靈機
- 圖靈機基礎 (TM)
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性有界自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
多磁帶圖靈機
多磁帶圖靈機有多個磁帶,每個磁帶都有一個單獨的磁頭訪問。每個磁頭可以獨立於其他磁頭移動。最初,輸入在磁帶 1 上,其他磁帶為空白。首先,第一個磁帶被輸入佔用,其他磁帶保持空白。接下來,機器讀取磁頭下連續的符號,並且 TM 在每個磁帶上列印一個符號並移動其磁頭。

多磁帶圖靈機可以正式描述為一個 6 元組 (Q, X, B, δ, q0, F),其中 -
Q 是狀態的有限集合
X 是磁帶字母表
B 是空白符號
δ 是狀態和符號上的關係,其中
δ: Q × Xk → Q × (X × {左移, 右移, 不移})k
其中有 k 個磁帶
q0 是初始狀態
F 是最終狀態的集合
注意 - 每個多磁帶圖靈機都有一個等價的單磁帶圖靈機。
廣告