形式语言与自动机 6 正则表达式.ppt

形式语言与自动机
授课 人： 王 良 民MAIL:
1
2021/7/24
第六章 正则表达式
引例
正则表达式的形式定义

例题
正则表达式与有穷自动机的等价性


(1)首先说明如何把DFA转换成GNFA
(2)说明如何把GNFA转换成正则表达式
2
2021/7/24
例题1：：算术表达式：(5+4)×2, 值为18，是一个数字正则表达式：(0∪1)0*, 正则表达式的值是一个语言
注意：
(0∪1)0* 表示的是01后加任意多个0构成的字符串所组成的语言
0和1是集合{0}和{1}的缩写，就是{0}∪{1}, 这部分的值是语言{0, 1}
0*就是{0}*,其值为所有包含任意个0的字符串构成的语言
在正则表达式中省略了连结运算符号o, (0∪1)0*实际上是(0∪1) o0*
正则表达式可以用来描述满足“某种模式”的字符串。
3
2021/7/24
很多应用程序及现代程序设计语言、文本编辑程序都提供用正则表达式描述模式的手段。
例题2：正则表达式(0∪1)*
其值为：由0和1的所有字符串组成的语言，也表示为{0, 1}*
表示方法：记∑为字母表，∑也可以表示该字母表中所有长度为1的字符串，而∑*为由该字母表中所有字符串组成的语言。
如：(0∑*)∪(∑*1)表示所有以0开头而以1结尾的字符串
正则运算的优先级：先星号，后连结，最后并，要改变这种惯常的顺序需要用括号。
4
2021/7/24
第六章 正则表达式
引例
正则表达式的形式定义

例题
正则表达式与有穷自动机的等价性


(1)首先说明如何把DFA转换成GNFA
(2)说明如何把GNFA转换成正则表达式
5
2021/7/24
定义 称R是一个正则表达式，如果R是
a, 这里a是字母表∑中的一个元素；
ε；
φ；
(R1∪R2)，这里R1和R2是正则表达式；
(R1oR2)，这里R1和R2是正则表达式；
(R1*)，这里R1是正则表达式；
6
2021/7/24
说明：
在(1)和(2)中，a和ε分别表示{ a }和{ε}
在(3)条中，φ表示空语言
在第(4)、(5)、(6)表示通过正则运算并、连结和星号获得正则表达式
（用较小的正则表达式定义较大的正则表达式，是归纳定义中的归纳步骤）
此处ε和φ的区别：有一个空语句的语言，和空语言
要想明显的区分正则表达式R和它所表示的语言时，后者用L(R)表示。
7
2021/7/24
第六章 正则表达式
引例
正则表达式的形式定义

例题
正则表达式与有穷自动机的等价性


(1)首先说明如何把DFA转换成GNFA
(2)说明如何把GNFA转换成正则表达式
8
2021/7/24
例题3：在下面的句子中，字母表为{0,1}
9
2021/7/24
例题4：设R是任意的正则表达式，有下述恒等式成立。
几个正则表达式的恒等式
这些恒等式有助于对正则表达式定义的理解
R∪φ = R
空语言加上任何一个语言不改变这个语言
Roε = R
空串加上任何一个字符串上不改变这个字符串
但是：R∪ε不一定等于R，Roφ不一定等于R
10
2021/7/24