DFA (确定有限自动机)

• DFA 指的是确定有限自动机。确定性是指计算的唯一性。如果机器一次读取一个输入字符串的符号，则有限自动机称为确定有限自动机。
• 在 DFA 中，对于从当前状态到下一个状态的特定输入，只有一条路径。
• DFA 不接受空移动，即 DFA 不能在没有任何输入字符的情况下改变状态。
• DFA 可以包含多个最终状态。它用于编译器中的词法分析。

在下图中，我们可以看到，从状态 q0 对于输入 a，只有一条路径通往 q1。同样，从 q0 开始，对于输入 b，只有一条路径通往 q2。

DFA 的形式定义

DFA 是一个 5 元组的集合，与我们在 FA 的定义中描述的相同。

转移函数可以定义为

DFA 的图形表示

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

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

示例 1

解决方案

转换图

转移表

示例 2

DFA with ∑ = {0, 1} 接受所有以 0 开头的字符串。

解决方案

说明

• 在上图中，我们可以看到，在状态 q0 中给定 0 作为输入到 DFA 时，DFA 将状态更改为 q1，并且始终在起始输入 0 时转到最终状态 q1。它可以接受 00, 01, 000, 001....等等。它不能接受任何以 1 开头的字符串，因为它永远不会转到以 1 开头的字符串的最终状态。

示例 3

DFA with ∑ = {0, 1} 接受所有以 0 结尾的字符串。

解决方案

说明

在上图中，我们可以看到，在状态 q0 中给定 0 作为输入到 DFA 时，DFA 将状态更改为 q1。它可以接受任何以 0 结尾的字符串，如 00, 10, 110, 100....等等。它不能接受任何以 1 结尾的字符串，因为它永远不会在 1 输入时转到最终状态 q1，因此以 1 结尾的字符串将不被接受或将被拒绝。