数据结构
网络
关系数据库管理系统
操作系统
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+ 次查看
