编译原理学习之：正则表达式（regular expression）和非正则语言（non

您所在的位置：网站首页 › 联立方程组求解正则表达式怎么写的 › 编译原理学习之：正则表达式（regular expression）和非正则语言（non

编译原理学习之：正则表达式（regular expression）和非正则语言（non

2024-07-13 03:10:54| 来源: 网络整理| 查看: 265

文章目录回顾子集构造（NFA → \rightarrow →DFA）正则语言的闭包结果正则语言的 Union 依然是正则语言正则语言的 concatenate ○ ○ ○ 操作依然是正则的正则语言的 k l e e n e s t a r kleene~ star kleene star 依然是正则语言正则语言的其他闭包性质如何构造 DFA 的运算算法（构造 DFA 的交、并、补集）如何构造最小的 DFA（指包括最少状态数的 DFA）构造最小化 DFA 举例正则表达式正则表达式语法和语义正则表达式举例正则表达式和自动机（Regular Expression VS. Automata）构造单个起始状态的 NFA正则语言 → \rightarrow → NFA 举例（单个起始状态）： ( a ∪ b ) ∗ b c (a ∪ b)^∗bc (a∪b)∗bc 构造单个 accept 状态的 NFA（兴趣读物：国内课本的方法）通过正则语言构造 NFA正则语言 → \rightarrow → NFA 举例化简 “单个” 起始和 accept 状态的 NFA扩展正则表达式的定理正则语言的局限性通过泵引理（Pumping Lemma）来验证正则语言泵引理反证法实例

回顾子集构造（NFA → \rightarrow →DFA）

在这里插入图片描述

正则语言的闭包结果正则语言的 Union 依然是正则语言 A , B A,B A,B 是两个正则语言，他们通过 ϵ \epsilon ϵ 组成了一个 NFA ，他可以表示为 A ∪ B A\cup B A∪B；我们要在状态开始的时候使用 ϵ \epsilon ϵ 来连接两个 DFA 在这里插入图片描述

正则语言的 concatenate ○ ○ ○ 操作依然是正则的

在这里插入图片描述

图中下半部分表示第一个语言的某两种状态通过 ϵ \epsilon ϵ 进行 concate 组成了第二种语言的某种状态；这样组成的新语言依然是正则语言正则语言的 k l e e n e s t a r kleene~ star kleene star 依然是正则语言

在这里插入图片描述

正则语言的其他闭包性质两个正则语言的 intersection（交集）依然是正则语言正则语言的补集（complement）依然是正则语言 A , A C A, A^C A,AC正则语言的差集（difference）依然是正则语言 A ∖ B A \setminus B A∖B正则语言的取反（reversal）依然是正则语言如何构造 DFA 的运算算法（构造 DFA 的交、并、补集）

在这里插入图片描述

如何构造最小的 DFA（指包括最少状态数的 DFA）因为我们无法保证通过某种算法可以得到最小的 DFA，如下图所示，我们不知道他是否为最简 DFA但是由于 DFA 拥有唯一的起始状态，并且转移函数是固定的，因此我们可以测试两个 DFA 的等价性从而找出最小的 DFA 在这里插入图片描述

要构造最小的 DFA 要不断重复以下步骤翻转 NFA确定化结果再翻转再次确定化结果翻转 NFA 的方式也很简单：那就是将所有的状态上的线调转方向将接受（accept）状态节点和初始节点（start）互换在这里插入图片描述

构造最小化 DFA 举例

这是我们要最小化的 NFA, 我们在下面的步骤中通过它得到一个最小的 DFA 在这里插入图片描述

第一步：翻转（1节点和 2 节点的功能互换，原本 1 是初始节点，2是accept 节点，现在调转一下 1 变成了 accept 节点，2 变成了初始节点）在这里插入图片描述

第二步：通过调转的 NFA 进行确定化得到当前状态下的 determinism 的结果在这里插入图片描述

因为最终状态中 5 , 6 5,6 5,6 包含原来的 1 1 1 状态（即 accept 状态），因此， 5 , 6 5,6 5,6 应该被标定为出口

第三步再次调转已经得到的 NFA ； 5 , 6 5,6 5,6 变成了起始状态； 4 4 4 变成了 accept 状态在这里插入图片描述

第四步：重复第二步的 determinism 得到最后的状态在这里插入图片描述

正则表达式各种编程语言中几乎都涉及正则表达式 ( 0 ∪ 1 ) ( 0 ∪ 1 ) ( 0 ∪ 1 ) ( ( 0 ∪ 1 ) ( 0 ∪ 1 ) ( 0 ∪ 1 ) ) ∗ (0 ∪ 1)(0 ∪ 1)(0 ∪ 1)((0 ∪ 1)(0 ∪ 1)(0 ∪ 1))^∗ (0∪1)(0∪1)(0∪1)((0∪1)(0∪1)(0∪1))∗ 代表一个长度为 3 的倍数的非空字符串 ∗ * ∗ 运算的优先级高于 concatenate；concatenate 高于 union 正则表达式语法和语义

在这里插入图片描述

正则表达式举例

在这里插入图片描述

正则表达式和自动机（Regular Expression VS. Automata）构造单个起始状态的 NFA 正则表达式和有限状态的自动机是等价的，而且有限状态机的起始状态只能有一个在下面的例子中，我们假设每个 NFA 的起始状态只有一个，那么对于一个多起始状态的 NFA N N N 我们可以表示成若干个 N ′ N^{'} N′ 的通过 ϵ \epsilon ϵ 的并联在这里插入图片描述

这个式子 δ ′ ( q , v ) \delta^{'}(q,v) δ′(q,v) 中， q i q_i qi 代表的就是原本的多个起始状态 q q q 统一用 q i q_i qi + ϵ \epsilon ϵ 代替；而其他不是起始状态开始的节点则遵循原本的 δ \delta δ 转换状态。在这里插入图片描述

正则语言 → \rightarrow → NFA 举例（单个起始状态）： ( a ∪ b ) ∗ b c (a ∪ b)^∗bc (a∪b)∗bc 国外的书籍和课件是按照这种方式进行构造和转换的在这里插入图片描述

构造单个 accept 状态的 NFA 可以看到下图的 N N N 中有 3 个终止状态汇总起始状态和将初始状态分开都同样使用 ϵ \epsilon ϵ例如下图的例子：在这里插入图片描述

图中的 δ ′ ( q , v ) \delta^{'}(q,v) δ′(q,v) 代表的就是将状态转换函数分成了两类：如果是原来 accept 状态，那么就添加一个新的状态 q f q_f qf 并且把原来所有的 accept 状态都通过 ϵ \epsilon ϵ 连接过去原来的其他状态则不需要进行调整，维持原本的样子所以我们看到下图中的三个原本的 accept 状态都通过 ϵ \epsilon ϵ 连到了新的 “唯一的 accpet” 状态 q f q_f qf 在这里插入图片描述

（兴趣读物：国内课本的方法）通过正则语言构造 NFA 当我们获得一个正则语言，我们如果要构造 NFA（单起始状态的），我们只需要不断重复下面三个步骤即可：（国内书籍版本）将 concatenate 操作分成两个串联的部分将 union （|）操作分成两个并联的部分将闭包运算 * 分成第三种情况在这里插入图片描述

正则语言 → \rightarrow → NFA 举例

在这里插入图片描述

化简 “单个” 起始和 accept 状态的 NFA 上文已经分别介绍了如何构造单个起始状态的 NFA 和单个 accept 状态的 NFA现在对于中间的状态进行重复地替换（使用正则表达式）以简化 NFA；方法就是把线上的字符用正则表达式来替换；并不断重复这个过程如下图所示，我们的 NFA 现在已经是单个起始状态和单个 accpet 状态；弧线上表示的 R 1 , R 2 , . . . R_1,R_2,... R1,R2,... 都是正则表达式，假设我们通过化简可以得到下面的两个 NFA 的表示 : ( R 1 ∪ R 2 R 3 ∗ R 4 ) ∗ R 2 R 3 ∗ (R_1 ∪ R_2R_3^∗R_4)^∗R_2R_3^∗ (R1∪R2R3∗R4)∗R2R3∗ R ∗ R^* R∗ 在这里插入图片描述