文档介绍：第三章
正则表达式与正则语言
1
§ 正则表达式（Regular expression,RE）
两个语言L和M的连接，记作，定义为
则明显地，
两个语言L和M的并，记作，为集合并
语言类的运算：设L，M 为上的语言，则
2
语言L的Kleene闭包，记作定义为
其中归纳定义为
例如：
为的Kleene闭包。
§ 正则表达式（Regular expression,RE）
3
正则表达式（递归定义）：
（1）是上的正则表达式，它表示语言，即。
（2）是上的正则表达式，它表示语言，即。
§ 正则表达式（Regular expression,RE）
的语言：
定义设
是一个字母表，
上的正则表达式E与所代表
（3），是正则表达式，它表示语言。
4
（4）如果E和F分别是上的正则表达式，则表示的语言为L(E) 和L(F)，
E和F的“和”（E+F)是上的正则表达式且
L(E+F)=L(E)∪L(F)。
E和F的“乘积”（EF）是上的正则表达式且L(EF)=L(E)L(F)。
E的克林闭包是上的正则表达式且
。
（5）只有满足（1）—（4）的表达式才是上的正则表达式。
§ 正则表达式（Regular expression,RE）
5

0是正则表达式，表示语言。
1是正则表达式，表示语言。
(0+1)是正则表达式，表示语言。
（01）是正则表达式，表示语言。
是正则表达式，表示所有以01结尾的字符串组成的语言。
§ 正则表达式（Regular expression,RE）
6
，它表示了交替0和1的串的集合。
例如：1010101，010101 等等
§ 正则表达式（Regular expression,RE）
7
正则表达式的运算优先级规定如下：
1）星运算符有最高优先级；
2）下一个运算级是连接运算符（乘积）；
3）并（和）是最低级。
例如：
§ 正则表达式（Regular expression,RE）
8
§ 有穷自动机和正则表达式
已证明DFA,NFA, 识别的语言类是一致的，下面进一步证明它们和正则表达式的语言也是一致的。
如果对于某个DFA A, L=L(A)，则存在一个正则表达式R,使得L=L(R)。
证明设DFA

令
9
§ 有穷自动机和正则表达式
即是所有那些将DFA从给定状态引导到状态，并且“途中”不经过（进入并离开）下标大于k的状态的所有字符串。但i,j不受k的限制。
这样是所有可以将DFA从状态引导到状态的字符串的集合。这时可递归定义为：
10