資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究區分非確定性、確定性和圖靈機計算模型？
讓我們從理解計算理論 (TOC) 中確定性有限自動機 (DFA) 的概念開始。
確定性有限自動機 (DFA)
在 DFA 中，對於每個輸入符號，都可以確定機器將移動到的狀態。因此，它被稱為確定性自動機。
形式化定義 - 確定性有限自動機是 5 元組
M=(Q, ∑, δ,q0,F)
其中，
Q - 有限狀態集。
∑ - 有限字母表集。
δ - Q × ∑ → Q 是轉移函式。
q0 ∈ − Q 是起始或初始狀態。
F - 終止或接受狀態。
非確定性有限自動機 (NDFA)
在 NDFA 中，對於特定的輸入符號，機器可以移動到機器中任何狀態的組合。總而言之，無法確定機器移動到的特定狀態。因此，它被稱為非確定性自動機。
形式化定義 - NDFA 也與 DFA 具有五個相同的狀態，但轉移函式不同，如下所示 -
δ: Q X ∑ -> 2Q
其中，
Q - 有限狀態集。
∑ - 輸入符號的有限集。
q0 - 初始狀態。
F - 終止狀態。
δ - 轉移函式。
非確定性下推自動機 (NPDA)
非確定性下推自動機非常類似於 NDFA。我們將討論一些承認 NPDA 的上下文無關文法 (CFG)。
承認確定性 PDA (DPDA) 的 CFG 也承認非確定性 PDA。從本質上講，有些 CFG 只能被 NPDA 識別，而不能被 DPDA 識別。
因此，NPDA 比 DPDA 更強大。
圖靈機
圖靈機 (TM) 是一種數學模型，它包含一條無限長的帶，該帶被劃分為單元格，並在其上給出資訊。
形式化定義
圖靈機是 7 元組 (Q, ∑, Γ, δ, q0, qaccept , qreject)
其中，
Q 是有限狀態集。
∑ 是輸入字母表，不包含空白符號 t。
Γ 是帶字母表，其中 t ∈ Γ 且 ∑ ⊆ Γ。
δ: (Q × Γ) → (Q × Γ × {L, R}) 是轉移函式。
q0 ∈ Q 是起始狀態。
qaccept ∈ Q 是接受狀態。
qreject ∈ Q 是拒絕狀態，其中 qreject ≠ qaccept。
差異
DFA 中沒有空字串轉換，而在 NDFA 中允許空字串轉換。
DFA 和 NDFA 中允許回溯，但圖靈機中不總是可能的。
NPDA 比有限狀態機更強大，但比圖靈機更弱。
1K+ 次檢視
