
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- Moore 機與 Mealy 機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的 Pumping 引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的閉包性質
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的 Pumping 引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 從 CFG 構造 PDA
- 下推自動機與解析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性界自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
非確定性圖靈機
在非確定性圖靈機中,對於每個狀態和符號,圖靈機都有一組可以執行的操作。因此,這裡的轉換不是確定性的。非確定性圖靈機的計算是一個從起始配置可以到達的配置樹。
如果樹中至少有一個節點是接受配置,則接受輸入,否則不接受。如果計算樹的所有分支在所有輸入上都停止,則非確定性圖靈機稱為**判定器**,如果對於某些輸入,所有分支都被拒絕,則該輸入也被拒絕。
非確定性圖靈機可以正式定義為一個 6 元組 (Q, X, ∑, δ, q0, B, F),其中 -
Q 是一個有限的狀態集
X 是帶字母表
∑ 是輸入字母表
δ 是一個轉移函式;
δ : Q × X → P(Q × X × {左移, 右移}).
q0 是初始狀態
B 是空白符號
F 是最終狀態集
廣告