解释确定性有限自动机 (DFA) 中的连接过程

下面解释确定性有限自动机 (DFA) 中的连接过程：

如果 L1 和 L2 是两个正则语言，则它们的交集 L1 ∩ L2 也是正则的。

例如：

L1 = {an | n > 0} 和 L2 = {bn | n > 0}

L3 = L1 ∩ L2 = {an ∩ bn | n > 0} 也是正则的。

在这个属性中，我们说两个 DFA 的连接也是 DFA。

问题

设计一个在字母表 {a,b} 上的 DFA，其中字符串以 'a' 开头并以 'b' 结尾。

解决方案

对于给定的条件，会形成两种不同类型的语言，如下所示：

• L1 = {a, aab, aabab, .......}
• L2 = {b, bbab, bbabab, .......}

在 L1 中，起始元素是 'a'，

在 L2 中，结束元素是 'b'。

语言 L1

它以 'a' 开头

L1 = {a, aab, aabab, .......}

L1 的状态转换图如下所示：

在上图的状态转换图中，q1 是初始状态。

DFA 中的每个状态都必须对两种输入产生转换

所以：

• q1 对 'a' 转到 q3 并达到其最终状态 {a}。

• q1 对 'b' 转到 q2 并达到死状态。

• q3 对 'a' 转到 q3，达到最终状态，生成从起始状态生成的字符串 {a,ab,aba,aab,abb,……} 满足每个字符串都以 'a' 开头的条件。

• q2 是死状态。

语言 L2

它以 'b' 结尾

L2 = {b, bbab, bbabab, .......}

L2 的状态转换图如下所示：

初始状态 q1：q1 对 'a' 转到 q1

        q1 对 'b' 转到 q2

一旦我们生成字符串 {ab,abb,abab,……}，它就满足语言中每个字符串都以 'b' 结尾的条件。

连接 L1 和 L2

当我们将 L1 和 L2 连接起来时，我们得到以下结果：

L = L1 ∩ L2 = L1.L2 = {ab, aab, abb, aaab, ...}

L1 和 L2 连接后的状态转换图如下所示：

Bhanu Priya

更新于：2021年6月15日

3K+ 浏览量

启动您的职业生涯

完成课程获得认证

开始学习