在理论计算机科学中解释确定性有限自动机。

DFA 指的是确定性有限自动机。确定性指的是计算的唯一性。如果机器一次读取一个输入符号的输入字符串，则有限自动机是确定性 FA。

在 DFA 中，从当前状态到下一状态只有一个路径输入。它不接受空移动，即它不能在没有任何输入的情况下更改状态。它可以包含多个最终状态。它用于编译器中的词法分析。

不同自动机（DFA）的形式化定义

确定性有限自动机 (DFA) 是一个集合，定义为 5 元组，如下所示：

M=(Q, Σ, δ,q0,F)

其中，

• Q：称为状态的有限集。
• Σ：称为字母表的有限集。
• δ：Q × Σ → Q 是转移函数。
• q0 ∈ Q 是起始状态或初始状态。
• F：最终状态或接受状态。

DFA 的图形表示

DFA 可以用称为状态图的有向图表示。

DFA 中考虑以下因素：

• 状态由顶点表示。
• 用输入字符标记的弧表示转换。
• 初始状态用箭头表示。
• 最终状态用双圆圈表示。

DFA 中的陷阱状态

如果转换到一个它永远无法逃脱的状态。这种状态称为陷阱状态。它被称为死状态。

在上面的例子中，q2 是一个陷阱状态或死状态，因为它无法到达最终状态。

DFA（确定性有限自动机）的应用

确定性有限自动机的不同应用如下：

• 协议分析文本解析。
• 电子游戏角色行为。
• 安全分析。
• CPU 控制单元。
• 自然语言处理语音识别等。

示例

为给定图构造 DFA 的转换表。

Q= {q0,q1,q2}

Σ ={0,1}

q0= {q0}

F= {q2}

转换图

转换图如下所示：

转换表

转换表如下所示：

解释

• 步骤 1 - 在上表中，q0 是初始状态，输入“0”时，q0 状态转到自身，输入“1”时，它转到状态 q1。
• 步骤 2 - q1 是中间状态，输入“0”时，q1 转到 q2 状态，输入“1”时，q1 转到自身。
• 步骤 3 - q2 是最终状态，q2 在“0”上转到 q2 本身，输入“1”转到 q2 本身。

Bhanu Priya

更新于： 2021 年 6 月 11 日

18K+ 浏览量

启动你的 职业生涯

通过完成课程获得认证

开始