
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- Moore 機與 Mealy 機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的抽吸引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的閉包性質
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的抽吸引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 由 CFG 構造 PDA
- 下推自動機和語法分析
- 圖靈機
- 圖靈機 (TM) 的基礎知識
- 圖靈機接受的語言
- 多帶圖靈機
- 多軌圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性界限自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
多軌圖靈機
多軌圖靈機是一種特殊的多種圖靈機,它包含多條磁帶,但只有一個磁頭在所有磁帶上讀寫。在這裡,單個磁頭在一步驟中從n條磁軌讀取n個符號。它接受遞迴可列舉語言,就像普通的單軌單帶圖靈機一樣。
多軌圖靈機可以形式化地描述為一個 6 元組 (Q, X, ∑, δ, q0, F),其中:
Q 是有限的狀態集
X 是磁帶字母表
∑ 是輸入字母表
δ 是狀態和符號上的關係,其中
δ(Qi, [a1, a2, a3,....]) = (Qj, [b1, b2, b3,....], 左移或右移)
q0 是初始狀態
F 是最終狀態集
注意 - 對於每個單軌圖靈機S,都存在一個等價的多軌圖靈機M,使得L(S) = L(M)。
廣告