文章目录

• 一、正则表达式 定义
• 二、 正则表达式语言 原子定义
• 三、正则表达式语言 结构归纳定义
• 四、正则表达式语言 示例
• 五、空集 ∅ \varnothing ∅ 与 空字符 ε \varepsilon ε 差别
• 六、正则表达式 定理
• 七、根据 正则表达式 语言 构造 自动机 ( 定理正向证明 )
• 八、构造原子自动机
• 九、使用 原子自动机 拼装 正则表达式对应的自动机

一、正则表达式 定义

---

1 . 正则表达式原子定义 :

如果 R R R 是

• 字符集 Σ \Sigma Σ 中的 1 1 1 个字符 ,
• 空字符串 ε \varepsilon ε , 或
• 空集 { ∅ } \{ \varnothing \} {∅} ,

那么称 R R R 是正则表达式 ;

2 . 正则表达式递归定义 :

如果 R 1 , R 2 R_1 , R_2 R1​,R2​ 是正则表达式 , 那么

• R 1 ∪ R 2 R_1 \cup R_2 R1​∪R2​ 是正则表达式 ;
• R 1 ∘ R 2 R_1 \circ R_2 R1​∘R2​ 是正则表达式 ;
• R 1 ∗ R_1^* R1∗​ 是正则表达式 ;

上述是正则表达式的定义 , 这是一个结构归纳定义 ;

二、 正则表达式语言 原子定义

---

正则表达式语言表示方式 : R R R 是正则表达式 , L ( R ) L(R) L(R) 是正则表达式代表的语言 ;

1 . 单个字符代表的语言 :

L ( a ) = { a } L(a) = \{a\} L(a)={a}

a a a 是字符集中的字符 , 那么其所代表的的语言是 { a } \{a\} {a} 单元集 , 是由一个元素的字符构成的 ;

2 . 空字符串代表的语言 :

L ( ε ) = { ε } L(\varepsilon) = \{ \varepsilon \} L(ε)={ε}

如果 ε \varepsilon ε 是正则表达式 , 其所代表的的语言 L ( ε ) L(\varepsilon) L(ε) , 是由空字符串组成的集合 { ε } \{ \varepsilon \} {ε} ;

3 . 空集代表的语言 :

L ( ∅ ) = ∅ L(\varnothing) = \varnothing L(∅)=∅

空集 ∅ \varnothing ∅ 所代表的的语言 , 就是空集 ;

三、正则表达式语言 结构归纳定义

---

1 . 正则表达式并集 的 语言 :

L ( R 1 ∪ R 2 ) = L ( R 1 ) ∪ L ( R 2 ) L(R_1 \cup R_2) = L(R_1) \cup L(R_2) L(R1​∪R2​)=L(R1​)∪L(R2​)

R 1 , R 2 R_1 , R_2 R1​,R2​ 是两个正则表达式 , 其并集的语言 , 就是其 两个语言的并集 ;

2 . 正则表达式串联 的 语言 :

L ( R 1 ∘ R 2 ) = L ( R 1 ) ∘ L ( R 2 ) L(R_1 \circ R_2) = L(R_1) \circ L(R_2) L(R1​∘R2​)=L(R1​)∘L(R2​)

R 1 , R 2 R_1 , R_2 R1​,R2​ 是两个正则表达式 , 其串联运算结果正则表达式的语言 , 就是其 两个正则表达式语言的 串联运算结果 ;

3 . 正则表达式星运算 的 语言 :

L ( R ∗ ) = ( L ( R ) ) ∗ L(R^*) = ( L(R) ) ^* L(R∗)=(L(R))∗

R R R 正则表达式 星运算 结果 正则表达式 的语言 , 就是 R R R 正则表达式的语言 进行 星运算的结果 ;

四、正则表达式语言 示例

---

字符集 : Σ = { 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 , 1 0,1 0,1 有限个字符串组成的字符 ;

正则表达式表示的语言 , 刚好是自动机所识别的语言 ; 可以根据该语言将自动机设计出来 ;

五、空集 ∅ \varnothing ∅ 与 空字符 ε \varepsilon ε 差别

---

空集 ∅ \varnothing ∅ 是正则表达式 , 类似于数中的 0 0 0 ;

空字符 ε \varepsilon ε 是正则表达式 , 类似于数中的 1 1 1 ;

( 后续待补充 )

六、正则表达式 定理

---

1 . 定理 : 一个语言如果是正则语言 , 当且仅当 , 该语言可以通过正则表达式表示出来 ;

2 . 有以下两层含义 :

• ① 正则表达式 -> 自动机识别 :正则表达式 表达出的语言 刚好 能够被自动机识别 ;

• ② 自动机识别 -> 正则表达式 : 自动机识别某个语言 , 那么该语言可以被正则表达式表达出来 ;

3 . 定理证明 :

① 正则表达式 -> 自动机识别 证明 : 给定一个正则表达式 , 设计一个自动机 , 该自动机所 接受 ( 识别 / 认识 ) 的语言 , 刚好是该正则表达式所表达的语言 ;

下面的 " 根据 正则表达式 语言 构造 自动机 " 小节的示例 , 证明了正则表达式语言必有自动机识别 ;

② 自动机识别 -> 正则表达式 证明 : 给定一个自动机 , 找到其所识别的 正则表达式语言 ;

七、根据 正则表达式 语言 构造 自动机 ( 定理正向证明 )

---

1 . 需求 : 根据下面的 正则表达式 构造 非确定性有限自动机 ( NFA ) , 刚好能 识别上述正则表达式表示的语言 ;

( a b ∪ a ) ∗ ( ab \cup a )^* (ab∪a)∗

构造能识别 ( a b ∪ a ) ∗ ( ab \cup a )^* (ab∪a)∗ 语言 的 自动机 ;

八、构造原子自动机

---

构造原子自动机 : 先构造能接收 单个字符 的自动机 ;

① 接收 a a a 字符的自动机 : 下面的自动机是可以识别 a a a 字符串的 ;

② 接收 b b b 字符的自动机 : 下面的自动机是识别 b b b 字符串的 ;

九、使用 原子自动机 拼装 正则表达式对应的自动机

---

拼装上述识别单个字符的 自动机 :

1 . 摆放自动机位置 : 将 2 2 2 个能识别 a a a 字符串的自动机 , 与 1 1 1 个能识别 b b b 字符串的自动机 , 按照如下排列放置 ;

2 . a b ab ab 对应自动机构造 :

① 自动机连接方式 : a a a 正则表达式语言 自动机 与 b b b 正则表达式语言 自动机 是串联在一起的 ;

② 串联两个自动机的状态 : 使用 ε \varepsilon ε 箭头 , 串联 a a a 对应自动机的接受状态 -> b b b 对应自动机的开始状态 ;

③ 修改 前者 的状态 : 同时将 a a a 对应自动机的接受状态 改为非接受状态 ;

下面是 a b ab ab 正则表达式 表达的语言 对应的自动机表示 :

3 . a b ∪ a ab \cup a ab∪a 对应自动机构造 :

① 添加新开始状态 : 重新添加一个开始状态 ;

② 连接并运算前者 : 使用 ε \varepsilon ε 箭头 从这个新添加的开始状态 指向 a b ab ab 自动机开始状态 ;

③ 连接并运算后者 : 使用 ε \varepsilon ε 箭头 从这个新添加的开始状态 指向 a a a 自动机开始状态 ;

下面是 a b ∪ a ab \cup a ab∪a 正则表达式 表达的语言 对应的自动机表示 :

4 . ( a b ∪ a ) ∗ ( ab \cup a )^* (ab∪a)∗ 对应自动机构造 :

① 构造方法 : 就是 在 ( a b ∪ a ) ( ab \cup a ) (ab∪a) 对应自动机的基础上 , 使用 ε \varepsilon ε 箭头 , 从 接受状态 指向 开始状态 ;

② 连接个数 : 所有的接受状态 , 都 使用 ε \varepsilon ε 箭头 指向开始状态 , 这里有两个接受状态 , 需要都指向开始状态 ;