2.3 正则表达式 主要内容： １．正则表达式和正则集； ２．正则表达式和有限自动机的相互转化。.

Presentation on theme: "2.3 正则表达式 主要内容： １．正则表达式和正则集； ２．正则表达式和有限自动机的相互转化。."— Presentation transcript:

1 2.3 正则表达式 主要内容： １．正则表达式和正则集； ２．正则表达式和有限自动机的相互转化。

2 一、正则表达式和正则集 描述程序设计语言中单词的一种简单而且数学化工具。 表示符号串的构成模式。
正则表达式r定义了一个符号串集合rs, rs内的每个符号串都与r所定义的模式相匹配，rs称为由r生成的语言，记作L(r)。 正则表达式所表示的符号串集合又称为正则集。 正则表达式是表示給定字母表上的符号串集合的一种工具。

3 （一）正则表达式和正则集的定义 定义1：设∑为有限字母表，在∑上的正则表达式和正则集可递归定义如下： (1)  和是∑上的正则表达式，它们表示的正则集分别为{ε}和； (2) 对任何a∈∑,a 是∑上的正则表达式，它所表示的正则集为{a}; (3) 若r,s都是正则表达式，它们表示的正则集分别为R和S, 则(r)、r|s、rs、(r)*也是正则表达式，它们分别表示的正则集是：R，R∪S , RS和R*。

4 注意： (4) 有限次使用上述三条规则构成的表达式，称为∑上的正则表达式，仅由这些正则表达式表示的集合称为正则集。
1.“|” 读作“或”，“” 读作“连接”，“ * ” 读作“闭包”。 2. “|” 、“” 和“ * ”的优先级为：先“ * ”、次“”、最后“|”。 3. “|” 、“” 和“ * ”的结合性为左结合。

5 是正则表达式，即  R其中L( )={ };
a  是正则表达式，即a  R其中L(a )={a}; 设Ａ和Ｂ是正则表达式，即Ａ R ，Ｂ R ，则有： 　 (A) R , L((A))= L(A) 　 A|B R , L(A|B)= L(A) ∪ L(B) A  B R , L(A  B)= L(A)L(B) 　 A* R , L(A*)= (L(A))*

6 上所有以a为首后跟任意多个（包括0个）b的字符串集
（二）正则表达式示例 ={ a,b }. 正则表达式e L(e) 1.a {a} 2.a|b {a, b} 3.ab { ab } 4.(a|b) (a|b) {aa, ab, ba, bb} 5. a* {ε,a,aa,aaaa,…} 6. a(b)* 上所有以a为首后跟任意多个（包括0个）b的字符串集 7.a(a|b)* 上所有以a为首的字符串集

7 （三）正则表达式的性质 正则表达式的等价 A | B = B | A | 的可交换性 A | (B | C) =(A | B ) C | 的可结合性 A (B C) =(A B )C 连接的可结合性 A (B | C) =A B | A C 连接的可分配性 (A | B ) C =A C | B C 连接的可分配性 A** =A* 幂的等价性 A  =  A=A 是连接的恒等元素

8 符号范围: [0--9] [a--z] [A--Z] 不在给定范围内的符号: ~(a|b|c)或[La] [Labc]
（四）扩充的正则表达式 一次或多次重复: A+ 任何符号: “…” 在字母表中任何符号. 符号范围: [0--9] [a--z] [A--Z] 不在给定范围内的符号: ~(a|b|c)或[La] [Labc] 0或1次(可选): r?=( |r)

9 为较长的正则表达式提供一个简化了的名字。例：为一个或多个数字组成的数字序列写一个正则表达式，则可写作：
（五）正则定义 为较长的正则表达式提供一个简化了的名字。例：为一个或多个数字组成的数字序列写一个正则表达式，则可写作： （0|1|2|3|4|5|6|7|8|9) （0|1|2|3|4|5|6|7|8|9)* 或写作 digit digit* 其中 digit就是数字的正则定义，表示为： digit = 0|1|2|3|4|5|6|7|8|9

10 identifier=letter(letter|digit)* 数字 整数Int＝[1-9]Digit*|0 实数real＝Int.Int
例：程序设计语言中单词的正则表达式定义 保留字 如 Begin＝begin 标识符 letter=[a-z，A-Z] digit=[0-9] identifier=letter(letter|digit)* 数字 整数Int＝[1-9]Digit*|0 实数real＝Int.Int 特殊符号 +|-|…

11 （六）正则表达式的局限性 正则表达式不能用于描述配对或嵌套的结构 正则表达式不能用于描述重复串 例：{w c w | w是a和b的串}无法用正则表达式表示（保证两边w是相同的）。

12 二、正则表达式和有限自动机的相互转化 定理 1 对∑上的每一个正则表达r，存在一个∑上的非确定有限自动机M，使得 L(M) = L(r) 。

13 证明：对于字母表∑上的任意一个正则表达式R,一定可以构造出一个非确定有限自动机 M, 使得L(M)=L(R)。
Step1:首先构造此非确定有限自动机M的初始状态S和终止状态Z,由S射出指向Z的有向弧上标记正则表达式R, step2:反复利用下述的替换规则对正则表达式R依次进行分解，直至状态转换图中所有有向弧上标记的符号都是字母表∑上的元素或为止。

14

15

16 例 ：有正规表达式(a|b)*aa, 为之构造等价的NFA。

17 定理2：对于字母表∑上的非确定有限自动机M，存在∑上的正则表达式R，使得L(R) = L(M)。
证明： Step1:在M的状态转换图中加入两个节点，一个是唯一的开始状态节点S,另一个是唯一的终止状态节点Z 。从S出发用标有ε的有向弧连接到M 的所有初始状态节点上，从M 的所有终止状态节点用标有ε的有向弧连接到Z节点. Step2:反复利用下述的替换规则进行替换，直到状态转换图中只剩下节点S和Z，在S指向Z的有向弧上所标记正则表达式就是所求的结果。

18 规则1及规则2：

19 规则3：

20 例 有如下图所示的NFA M,试构造与之等价的正则表达式r

21 单元总结 三个工具： 文法、 有限自动机、正则表达式 三个算法： 一个实现： DFA的实现 正则表达式与FA的相互转换 NFA到DFA的转换
文法、 有限自动机、正则表达式 三个算法： 正则表达式与FA的相互转换 NFA到DFA的转换 DFA的化简 一个实现： DFA的实现

22 作业 S={a,b,c} 试给出S-上一个不包含连续两个b的所有符号串集合的正则定义.
叙述正则式((b|c)*a(b|c)*a)*(b|c)* 描述的符号串 S ＝{0,1} 叙述正则式 (00 | 11) ( (01 | 10) (00 | 11)  (01 | 10 ) )  (00 | 11)  描述的符号串 给出能被5整除的二进制数表示形式的正则定义。