构建一个 Σ={0,1} 的 DFA，接受所有包含 0 的字符串。

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

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

其中，

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

示例 1

DFA 接受所有以 0 开头的字符串

语言 L= {0,01,001,010,0010,000101,…}

在这个语言中，所有字符串都以零开头。

状态转换图

状态转换图如下所示：

解释

• 步骤 1 - q0 是初始状态，输入 '0' 时，它转到 q1，这是结束状态，'0' 字符串被接受。
• 步骤 2 - q0 输入 '1' 时，转到 q2，这是死状态，因为对于 q2 没有路径可以到达结束状态。
• 步骤 3 - q1 输入 '0' 和 '1' 时，都转到 q1 本身，这是结束状态。

状态转换表

状态转换表如下所示：

示例 2

为接受以 '101' 开头的字符串的语言构建 DFA。

• 所有字符串都以子字符串“101”开头。
• 则子字符串的长度 = 3。

因此，DFA 中最小状态数 = 3 + 2 = 5。

最小化的 DFA 有五个状态。

语言 L= {101,1011,10110,101101,.........}

状态转换图如下所示：

解释

• 步骤 1 - q0 是初始状态，输入 '1' 时转到 q1，输入 '0' 时导致死状态。
• 步骤 2 - q1 输入 '0' 时转到 q2，输入 '1' 时转到死状态。
• 步骤 3 - q2 输入 '1' 时转到 qf，这是结束状态，输入 '0' 时转到死状态。
• 步骤 4 - qf 是结束状态，输入 '1' 和 '0' 时都转到 qf 本身。

Bhanu Priya

更新于: 2021年6月11日

30K+ 浏览量

开启你的 职业生涯

完成课程获得认证

开始学习