区分非确定性、确定性和图灵机计算模型？
让我们首先了解计算理论(TOC)中确定性有限自动机(DFA)的概念。
确定性有限自动机(DFA)
在DFA中，对于每个信息图像，可以决定机器将移动到的状态。此后，它被称为确定性自动机。
形式定义-确定性有限自动机是一个5元组
M=(Q,∑,δ,q0,F)
在哪里，
Q-称为状态的有限集。
∑-称为字母表的有限集。
δ−Q×∑→Q是转移函数。
q0∈−Q是开始或初始状态。
F-最终或接受状态。
非确定性有限自动机(NDFA)
在NDFA中，对于特定的信息图像，机器可以移动到机器中的任何状态组合。总而言之，无法解析机器移动到的具体状态。此后，它被称为非确定性自动机。
正式定义-NDFA也有五个与DFA相同的状态，但具有不同的转换函数，如下所示-
δ：QX∑->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。
差异
尽管在NDFA许可中，无效字符串更改在DFA中没有看到。
DFA和NDFA中允许回溯，但通常无法想象回溯。
NPDA比有限状态机更强大，但不如车削机。