绘制一个接受以“ab”开头的字符串的DFA。

问题

绘制一个在字母表Σ={a,b}上的状态转移图，该图接受以'ab'开头的字符串。

解答

确定性有限自动机 (DFA) 的形式化定义如下：

DFA 是一个由 5 元组组成的集合，如下所示：

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

其中，

• Q：有限状态集。
• Σ：有限字母表集。
• δ：Q × Σ → Q 是转移函数。
• q0 ∈ Q 是初始状态。

生成的语言如下所示：

L={ab,aba,abab,……}

状态转移图如下：

这里，

• D 是一个死状态。
• D 是一个转移状态，它永远无法逃脱。这种状态称为陷阱状态，也称为死状态。

示例 1

• **ab** - q1 在 'a' 上转移到 q2，q2 在 'b' 上转移到 qf 以达到最终状态。因此，ab 被接受。
• **baa** - q1 在 'b' 上转移到 D 状态，这是一个死状态。无法到达最终状态。因此，baa 未被接受。

转移表

转移表如下：

解释

• **步骤 1** - q1 是初始状态，输入 a 时它转移到状态 q2，输入 'b' 时转移到死状态。
• **步骤 2** - q2 在 'a' 上转移到死状态，在 'b' 上转移到 qf，这是最终状态。
• **步骤 3** - qf 是最终状态，输入 'a' 和 'b' 时都转移到 qf 状态本身。
• **步骤 4** - D 是死状态，从 D 没有路径到任何状态。

示例 2

设计一个 DFA，它接受字母表 Σ = {a, b} 上的语言，使得 L 是所有以 'aba' 开头的字符串的集合。

所有字符串都以子串“aba”开头。

因此，子串长度 = 3。

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

语言 L= {aba,abaa,abaab,abaaba}

状态转移图如下：

转移表

转移表如下：

Bhanu Priya

更新于：2021年6月11日

25K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习