文章目录
一、正则表达式 定义二、 正则表达式语言 原子定义三、正则表达式语言 结构归纳定义四、正则表达式语言 示例五、空集 ∅\varnothing∅ 与 空字符 ε\varepsilonε 差别六、正则表达式 定理七、根据 正则表达式 语言 构造 自动机 ( 定理正向证明 )八、构造原子自动机九、使用 原子自动机 拼装 正则表达式对应的自动机一、正则表达式 定义
1 . 正则表达式原子定义 :
如果 RRR 是
字符集 Σ\SigmaΣ 中的 111 个字符 ,空字符串 ε\varepsilonε , 或空集 {∅}\{ \varnothing \}{∅} ,
那么称 RRR 是正则表达式 ;
2 . 正则表达式递归定义 :
如果 R1,R2R_1 , R_2R1,R2 是正则表达式 , 那么
R1∪R2R_1 \cup R_2R1∪R2 是正则表达式 ;R1∘R2R_1 \circ R_2R1∘R2 是正则表达式 ;R1∗R_1^*R1∗ 是正则表达式 ;
上述是正则表达式的定义 , 这是一个结构归纳定义 ;
二、 正则表达式语言 原子定义
正则表达式语言表示方式 : RRR 是正则表达式 , L(R)L(R)L(R) 是正则表达式代表的语言 ;
1 . 单个字符代表的语言 :
L(a)={a}L(a) = \{a\}L(a)={a}
aaa 是字符集中的字符 , 那么其所代表的的语言是 {a}\{a\}{a} 单元集 , 是由一个元素的字符构成的 ;
2 . 空字符串代表的语言 :
L(ε)={ε}L(\varepsilon) = \{ \varepsilon \}L(ε)={ε}
如果 ε\varepsilonε 是正则表达式 , 其所代表的的语言 L(ε)L(\varepsilon)L(ε) , 是由空字符串组成的集合 {ε}\{ \varepsilon \}{ε} ;
3 . 空集代表的语言 :
L(∅)=∅L(\varnothing) = \varnothingL(∅)=∅
空集 ∅\varnothing∅ 所代表的的语言 , 就是空集 ;
三、正则表达式语言 结构归纳定义
1 . 正则表达式并集 的 语言 :
L(R1∪R2)=L(R1)∪L(R2)L(R_1 \cup R_2) = L(R_1) \cup L(R_2)L(R1∪R2)=L(R1)∪L(R2)
R1,R2R_1 , R_2R1,R2 是两个正则表达式 , 其并集的语言 , 就是其 两个语言的并集 ;
2 . 正则表达式串联 的 语言 :
L(R1∘R2)=L(R1)∘L(R2)L(R_1 \circ R_2) = L(R_1) \circ L(R_2)L(R1∘R2)=L(R1)∘L(R2)
R1,R2R_1 , R_2R1,R2 是两个正则表达式 , 其串联运算结果正则表达式的语言 , 就是其 两个正则表达式语言的 串联运算结果 ;
3 . 正则表达式星运算 的 语言 :
L(R∗)=(L(R))∗L(R^*) = ( L(R) ) ^*L(R∗)=(L(R))∗
RRR 正则表达式 星运算 结果 正则表达式 的语言 , 就是 RRR 正则表达式的语言 进行 星运算的结果 ;
四、正则表达式语言 示例
字符集 :Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} ;
正则表达式 :(0∪1)∗10(0∪1)∗( 0 \cup 1 )^* 1 0 ( 0 \cup 1 )^*(0∪1)∗10(0∪1)∗ ;
正则表达式转化成语言 :
L((0∪1)∗10(0∪1)∗)=L((0∪1)∗)∘L(1)∘L(0)∘L((0∪1)∗)={0,1}∗∘{1}∘{0}∘{0,1}∗\begin{array}{lcl} && L( ( 0 \cup 1 )^* 1 0 ( 0 \cup 1 )^* ) \\\\ &=& L( ( 0 \cup 1 )^* ) \circ L(1) \circ L(0) \circ L( ( 0 \cup 1 )^* ) \\\\ &=& \{0,1\}^* \circ \{ 1 \} \circ \{ 0 \} \circ \{ 0, 1 \}^* \end{array}==L((0∪1)∗10(0∪1)∗)L((0∪1)∗)∘L(1)∘L(0)∘L((0∪1)∗){0,1}∗∘{1}∘{0}∘{0,1}∗
上述 {0,1}∗\{0,1\}^*{0,1}∗ 就是 0,10,10,1 有限个字符串组成的字符 ;
正则表达式表示的语言 , 刚好是自动机所识别的语言 ; 可以根据该语言将自动机设计出来 ;
五、空集 ∅\varnothing∅ 与 空字符 ε\varepsilonε 差别
空集 ∅\varnothing∅ 是正则表达式 , 类似于数中的 000 ;
空字符 ε\varepsilonε 是正则表达式 , 类似于数中的 111 ;
( 后续待补充 )
六、正则表达式 定理
1 . 定理 : 一个语言如果是正则语言 , 当且仅当 , 该语言可以通过正则表达式表示出来 ;
2 . 有以下两层含义 :
① 正则表达式 -> 自动机识别 :正则表达式 表达出的语言 刚好 能够被自动机识别 ;
② 自动机识别 -> 正则表达式 :自动机识别某个语言 , 那么该语言可以被正则表达式表达出来 ;
3 . 定理证明 :
① 正则表达式 -> 自动机识别 证明 :给定一个正则表达式 , 设计一个自动机 , 该自动机所 接受 ( 识别 / 认识 ) 的语言 , 刚好是该正则表达式所表达的语言 ;
下面的 " 根据 正则表达式 语言 构造 自动机 " 小节的示例 , 证明了正则表达式语言必有自动机识别 ;
② 自动机识别 -> 正则表达式 证明 :给定一个自动机 , 找到其所识别的 正则表达式语言 ;
七、根据 正则表达式 语言 构造 自动机 ( 定理正向证明 )
1 . 需求 :根据下面的 正则表达式 构造 非确定性有限自动机 ( NFA ) , 刚好能 识别上述正则表达式表示的语言 ;
(ab∪a)∗( ab \cup a )^*(ab∪a)∗
构造能识别 (ab∪a)∗( ab \cup a )^*(ab∪a)∗ 语言 的 自动机 ;
八、构造原子自动机
构造原子自动机 :先构造能接收 单个字符 的自动机 ;
① 接收 aaa 字符的自动机 :下面的自动机是可以识别 aaa 字符串的 ;
② 接收 bbb 字符的自动机 :下面的自动机是识别 bbb 字符串的 ;
九、使用 原子自动机 拼装 正则表达式对应的自动机
拼装上述识别单个字符的 自动机 :
1 . 摆放自动机位置 :将 222 个能识别 aaa 字符串的自动机 , 与 111 个能识别 bbb 字符串的自动机 , 按照如下排列放置 ;
2 . ababab 对应自动机构造 :
① 自动机连接方式 :aaa 正则表达式语言 自动机 与 bbb 正则表达式语言 自动机 是串联在一起的 ;
② 串联两个自动机的状态 :使用 ε\varepsilonε 箭头 , 串联 aaa 对应自动机的接受状态 -> bbb 对应自动机的开始状态 ;
③ 修改 前者 的状态 :同时将 aaa 对应自动机的接受状态 改为非接受状态 ;
下面是 ababab 正则表达式 表达的语言 对应的自动机表示 :
3 . ab∪aab \cup aab∪a 对应自动机构造 :
① 添加新开始状态 :重新添加一个开始状态 ;
② 连接并运算前者 :使用 ε\varepsilonε 箭头 从这个新添加的开始状态 指向 ababab 自动机开始状态 ;
③ 连接并运算后者 :使用 ε\varepsilonε 箭头 从这个新添加的开始状态 指向 aaa 自动机开始状态 ;
下面是 ab∪aab \cup aab∪a 正则表达式 表达的语言 对应的自动机表示 :
4 . (ab∪a)∗( ab \cup a )^*(ab∪a)∗ 对应自动机构造 :
① 构造方法 :就是 在 (ab∪a)( ab \cup a )(ab∪a) 对应自动机的基础上 , 使用 ε\varepsilonε 箭头 , 从 接受状态 指向 开始状态 ;
② 连接个数 :所有的接受状态 , 都 使用 ε\varepsilonε 箭头 指向开始状态 , 这里有两个接受状态 , 需要都指向开始状态 ;
【计算理论】正则语言 ( 正则表达式原子定义 | 正则表达式递归定义 | 正则表达式语言原子定义 | 正则表达式语言结构归纳 | 正则表达式语言示例 | 根据正则表达式构造自动机 )
如果觉得《【计算理论】正则语言 ( 正则表达式原子定义 | 正则表达式递归定义 | 正则表达》对你有帮助，请点赞、收藏，并留下你的观点哦！
