第02章 形式语言与自动机理论(机械工业出版社)

1、主要内容：主要内容：l语言和文法语言和文法l有限自动机有限自动机l正则表达式正则表达式n语言和文法的关系语言和文法的关系 什么是语言？什么是语言？ 如何表述语言？如何表述语言？ 什么是程序设计语言？什么是程序设计语言？ 如何表述程序设计语言？如何表述程序设计语言？n基本概念基本概念l字母表字母表：元素的非空有穷集合。：元素的非空有穷集合。 l符号串符号串：由字母表中的符号组成的任何有穷序列。：由字母表中的符号组成的任何有穷序列。 或者如下定义：或者如下定义： 1. 空符号串空符号串是是 上的符号串上的符号串 2. 若若x是是 上的符号串上的符号串,a是是 的元素的元素,则则xa是是 上的符号串

2、上的符号串 3. y是是 上的符号串上的符号串,当且仅当它可以由当且仅当它可以由1和和2导出导出 思考如下问题：思考如下问题： 1. 符号串的长度如何定义？符号串的长度如何定义？ 2. 和和有何区别？有何区别？ 3. 如何判断两个符号串相等？如何判断两个符号串相等？l符号串的连接符号串的连接：设设x x和和y y 均是字母表均是字母表上的符号串，上的符号串，它们的连接是把它们的连接是把y y的所有符号顺序接在的所有符号顺序接在x x的符号之后的符号之后所得到的符号串。所得到的符号串。 l符号串的方幂符号串的方幂：设：设x是字母表是字母表上的符号串，把上的符号串，把x自自身连接身连接n次得到的符

3、号串次得到的符号串z, 称作符号串称作符号串x的的n 次幂，次幂，记作记作 z=xn ，特别地：特别地：x0= l前缀和后缀前缀和后缀：设：设x是字母表上的符号串，是字母表上的符号串，x=yz ,则则y是是x 的前缀，的前缀，z 是是x的后缀，特别是当的后缀，特别是当z 时，时，y是是x的真的真前缀；前缀；y时，时，z是是x的真后缀。的真后缀。l子字符串子字符串：非空字符串：非空字符串 x ,删去它的前缀和后缀后所删去它的前缀和后缀后所得到的字符串称为得到的字符串称为 x 的子字符串，简称子串。如果的子字符串，简称子串。如果删去的前缀和后缀不同时为删去的前缀和后缀不同时为,则称该子串为真子串。

4、则称该子串为真子串。l符号串集合符号串集合：若集合：若集合A A中的所有元素都是某字母表上中的所有元素都是某字母表上的符号串，则称的符号串，则称A A为该字母表上的符号串集合。为该字母表上的符号串集合。l符号串集合的乘积符号串集合的乘积：设设A、B 是两个符号串集合，是两个符号串集合，AB表示表示A与与B的乘积，则定义的乘积，则定义 AB=xy|(xA)(yB) l符号串集合的方幂符号串集合的方幂：设：设A是符号串集合，则称是符号串集合，则称Ai 是是符号串集合符号串集合 A的方幂，其中的方幂，其中i 是非负整数。是非负整数。 A0= , A1=A, A2=AA, , An=AA Al符号串集

5、合的正闭包符号串集合的正闭包：A+=A1 A2 A3 l符号串集合的星闭包符号串集合的星闭包：A*= A0 A1 A2 A3 n文法之概述文法之概述l文法能清晰地描述程序设计语言的语法构成易于文法能清晰地描述程序设计语言的语法构成易于理解。理解。l文法能自动地构造有效的语法分析器，检查源程文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。序是否符合语言规定的语法形式。l文法定义可以了解程序设计语言的结构，有利于文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检查出语法错误。将源程序转化为目标代码，以及检查出语法错误。l基于文法实现的语言易于扩展基于文

6、法实现的语言易于扩展n文法之定义文法之定义l文法文法G G定义为四元组定义为四元组( (V VT T,V,VN N,S,P,S,P) ) V VT T是有限的终极符集合是有限的终极符集合 V VN N是有限的非终极符集合是有限的非终极符集合 S S是开始符，是开始符，S S V VN N P P是产生式的集合，且具有下面的形式：是产生式的集合，且具有下面的形式： ，其中，其中 ，( (V VT T V VN N) )* *n文法之分类文法之分类lO O型文法型文法: : 也称为短语文法，其产生式具有形式也称为短语文法，其产生式具有形式: : ，其中，其中 , ,(V(VT T V VN N)

7、)* *，并且，并且 至少含一个非终至少含一个非终极符极符 。l1 1型文法型文法: : 也称为上下文相关文法。它是也称为上下文相关文法。它是0 0型文法的型文法的特例，要求特例，要求| | | | | | | (S| (S 例外，但例外，但S S不得出现于不得出现于产生式右部产生式右部) )。l2 2型文法型文法: : 也称为上下文无关文法。它是也称为上下文无关文法。它是1 1型文法的型文法的特例，即要求产生式左部是一个非终极符特例，即要求产生式左部是一个非终极符: A: A 。l3 3型文法型文法: : 也称为正则文法。它是也称为正则文法。它是2 2型文法的特例，型文法的特例，即产生式的右

8、部至多有两个符号，而且具有下面形即产生式的右部至多有两个符号，而且具有下面形式之一式之一: A a : A a ，A a BA a B其中其中A,BA,B V VN N ，a a V VT T 。 n上下文无关文法（上下文无关文法（CFGCFG）l定义为四元组定义为四元组(V(VT T,V,VN N,S,P),S,P) V VT T是有限的终极符集合是有限的终极符集合 V VN N是有限的非终极符集合是有限的非终极符集合 S S是开始符，是开始符，S S V VN N P P是产生式的集合，且具有下面的形式：是产生式的集合，且具有下面的形式： A AX X1 1X X2 2XXn n 其中其中

9、A A V VN N，X Xi i (V (VT T V VN N) ) ，右部可空。，右部可空。n文法相关概念文法相关概念l推导（直接推导）推导（直接推导）：如果：如果A A是一个产生式，是一个产生式，则有则有 A A , ,其中其中表示一步推导表示一步推导( (用用A A ) )。这时称。这时称是由是由 A A 直接推导的。直接推导的。 的的含义是，使用一条规则，代替含义是，使用一条规则，代替左边的某个左边的某个符号，产生符号，产生右端的符号串。右端的符号串。l + + : : 表示表示 通过一步或多步可推导出通过一步或多步可推导出 l * * : : 表示表示 通过通过0 0步或多步可推

10、导出步或多步可推导出 l句型句型： 如果有如果有S S* * ，则称符号串，则称符号串 为为CFGCFG的句的句型型 。我们用。我们用SF(G)SF(G)表示文法表示文法G G的所有句型的的所有句型的集合。集合。l句子句子： 如果如果 只包含终极符，则称只包含终极符，则称 为为CFGCFG的句子。的句子。l语言语言： L(G)= u| S + u ,u VT* 文法文法G G所定义的语言是其开始符所能推导的所定义的语言是其开始符所能推导的所有终极符号串所有终极符号串( (句子句子) )的集合。的集合。 l最左（右）推导最左（右）推导： 如果进行推导时选择的是句型中的最左如果进行推导时选择的是句

11、型中的最左( (右）右）非终极符，则称这种推导为最左非终极符，则称这种推导为最左( (右右) )推导，推导，并用符号并用符号lmlm（rmrm）表示最左（右）推导。）表示最左（右）推导。 l左（右）句型左（右）句型： 用最左推导方式导出的句型，称为左句型，用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型而用最右推导方式导出的句型，称为右句型( (规范句型规范句型) )。 结论：结论： 每个句子都有相应的最右和最左推导（但对每个句子都有相应的最右和最左推导（但对句型此结论不成立）句型此结论不成立） l短语短语：设设S S是文法的开始符，是文法的开始符，是句型是句型(

12、(即即有有S S * *），如果满足条件：），如果满足条件：S S * * A A A A + + 则称则称 是句型是句型的一个短语。的一个短语。 l直接短语（简单短语）直接短语（简单短语）：如果满足条件：如果满足条件：S S * * A A A A 则称则称 是句型是句型的一个简单短语。的一个简单短语。 l句柄句柄：一个句型可能有多个简单短语，其中一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。最左的简单短语称之为句柄。 q语法分析树语法分析树( (简称分析树简称分析树) )用来描述句型的结构，是用来描述句型的结构，是句型推导的一种树型表示。文法句型推导的一种树型表示。文法 G=(

13、VG=(VN N,V,VT T,S,P),S,P)，则，则称满足下面条件的树为称满足下面条件的树为G G的一棵分析树：的一棵分析树：1. 1. 每个结点都有每个结点都有G G的一个文法符号，并且根结点标的一个文法符号，并且根结点标 有初始符有初始符S S，非叶结点标有非终极符，叶结点标有，非叶结点标有非终极符，叶结点标有 终极符或非终极符或终极符或非终极符或 。 2.2.如果一个非叶结点如果一个非叶结点A A有有n n个儿子结点个儿子结点( (从左到右）为从左到右）为 X1,X2,.,XnX1,X2,.,Xn，则，则G G一定有产生式一定有产生式 AX1X2 .Xn AX1X2 .Xn 。l线

14、性推导线性推导：我们称用我们称用符号进行的推导为线性推导符号进行的推导为线性推导 。l树型推导与线性推导的不同：树型推导与线性推导的不同：线性推导指明了推导的线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。因此，句顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵分析树型一般只有一棵分析树( (如果无二义性如果无二义性) )，而线性推导，而线性推导则可很多。则可很多。n二义性文法二义性文法：如果一个文法的某个句型有两：如果一个文法的某个句型有两棵不同的语法分析树，则称该文法二义性为二棵不同的语法分析树，则称该文法二义性为二义性文法。义性文法。l文法文法G=( +,*,I,(

15、,), E, E, P),其中其中P为：为： E i E E + E E E * E E ( E )句型句型i*i+i:推导推导1: E E + E E * E + E i * E + E i * i + E i * i + i推导推导1: E E * E i * E i * E + E i * i + E i * i + i推导推导1的语法树的语法树E+EEE*EiiiEE*EE+Eii推导推导2的语法树的语法树in文法等价变换文法等价变换l增加拓广产生式增加拓广产生式 定理定理：对任一文法：对任一文法G1都可以构造文法都可以构造文法G2，使得，使得L(G1)=L(G2)，且，且G2的开始符

16、唯一且不出现于任何的开始符唯一且不出现于任何产生式的右部。产生式的右部。 证明证明：假设：假设S是是G1的开始符，则只要在的开始符，则只要在G1中扩充一中扩充一条新产生式条新产生式ZS即可，其中即可，其中Z是新的开始符。另这是新的开始符。另这样扩充后的文法为样扩充后的文法为G2，则它显然满足定理的要求。，则它显然满足定理的要求。 l消除空产生式消除空产生式定理定理：对任一文法：对任一文法G1，可构造文法，可构造文法G2，使得，使得L(G1)=L(G2)，且，且G2中无空产生式。中无空产生式。证明证明：根据：根据G1，构造，构造G2的方法如下：的方法如下： (1) 令令 =A | A (2) =

17、A | A + , +。(3) 从从G1中删除所有空产生式。中删除所有空产生式。(4) 从从G1中删除只能导出空串的非终极符。中删除只能导出空串的非终极符。(5) 对于文法中任意产生式对于文法中任意产生式AX1X2Xi-1XiXi+1Xn a.若若Xi VT，不做动作；，不做动作；b.若若Xi VN- ，不做动作；，不做动作；c.若若Xi，补充规则，补充规则A X1X2Xi-1Xi+1Xn；例：例： AaBcD Bb | DBB | dl消除不可达产生式消除不可达产生式定理定理：对任一文法：对任一文法G1都可以构造文法都可以构造文法G2，使得，使得L(G1)=L(G2)，且，且G2中的每个非终

18、极符必出现在它中的每个非终极符必出现在它的某个句型中。的某个句型中。证明证明：根据：根据G1，构造文法，构造文法G2的方法如下：的方法如下：(1) 令令 =Z | Z是文法的开始符是文法的开始符。(2) 递归扩充递归扩充 直到收敛为止，即直到收敛为止，即 =B | AxBy G1, B VN, A(3) 若一个产生式左部非终极符若一个产生式左部非终极符A，则删除以，则删除以A为为左部的所有产生式。左部的所有产生式。l消除特型产生式消除特型产生式定理定理：对任一文法：对任一文法G1，可以构造文法，可以构造文法G2，使得，使得L(G1)=L(G2)，且在，且在G2中没有特型产生式。中没有特型产生式

19、。证明证明：构造无特型产生式的文法：构造无特型产生式的文法G2的方法如下：的方法如下：(1) 对文法对文法G1中任意非终极符中任意非终极符A，求集合，求集合 A=B | A+B, B VN。(2) 若若BA，且，且B 是文法是文法G中的一个非特型产生中的一个非特型产生式，则补充如下规则式，则补充如下规则A 。(3) 去掉文法去掉文法G1中的所有的特型产生式。中的所有的特型产生式。(4) 去掉新的文法中的无用产生式。去掉新的文法中的无用产生式。例：例：AB | D | aBBC | bCcDB | dl消除文法二义性消除文法二义性S if E then S | if E then S else

20、S | Other该文法是一个二义性文法，与之等价的无二义性该文法是一个二义性文法，与之等价的无二义性的文法如下：的文法如下：S M | UM if E then M else M | OtherU if E then S | if E then M else Ul 消除公共前缀消除公共前缀某个非终极符某个非终极符A有如下的两个产生式：有如下的两个产生式： A ，A ( (即有左公共前缀即有左公共前缀) )消除方法：消除方法：1. 产生式形如：产生式形如：A1|2|n| 表示不以表示不以 开头的字符串。开头的字符串。2.引进非终极符引进非终极符A，使产生式替换为：，使产生式替换为： A A |

21、 A 1| 2 | nl消除左递归消除左递归一个文法含有下列形式的产生式时一个文法含有下列形式的产生式时（1） AA | A VN, a , (VN VT)*（2） A B | B A | b A,B VN, a , , (VN VT)*其中（其中（1 1）为）为直接左递归直接左递归，（，（2 2）为）为间接左递归间接左递归，因，因此文法中只要有此文法中只要有A+A，则称文法为左递归的。，则称文法为左递归的。（1 1）对直接左递归形如：）对直接左递归形如：A A | 消除左递归：消除左递归：A A A A | （2 2）间接左递归形如：）间接左递归形如：A B | B A | b 消除左递归：

22、消除左递归： 转为直接左递归形式：转为直接左递归形式：A A | b | 或者或者 B B | | b 按照直接左递归方式消除。去掉多余的按照直接左递归方式消除。去掉多余的 产生式。产生式。主要内容：主要内容：l确定有限自动机确定有限自动机DFA(Deterninistic FA)DFA(Deterninistic FA)l非确定有限自动机非确定有限自动机NFA(Nondeterninistic FA)NFA(Nondeterninistic FA)lNFANFA到到DFADFA的转换的转换lDFADFA的化简的化简n确定有限自动机确定有限自动机定义定义l确定有限自动机确定有限自动机DFA为一

23、个五元组为一个五元组( , S, S0, f, Z)，其，其中：中：u 是有穷字母表，每个元素称为一个输入字符；是有穷字母表，每个元素称为一个输入字符；uS是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；uS0 S是唯一的一个初始状态；是唯一的一个初始状态；uf是在是在 SS上的转换函数（单值）；上的转换函数（单值）；uZ SS，是终止状态集，又称为接受状态集；，是终止状态集，又称为接受状态集；n一个一个DFA的例子的例子 DFA M=(a, b, S, U, V, Q, f, S, Q)，其中，其中 f 定义为：定义为：f (S, a)=Uf (V, a)=U

24、f (S, b)=Vf (V, b)=Qf (U, a)=Qf (Q, a)=Qf (U, b)=Vf (Q, b)=QnDFA的两种表示方式的两种表示方式l 状态转换图状态转换图 结点表示状态，转换边表示转换函数，边结点表示状态，转换边表示转换函数，边 的箭头方向指向转换函数中定义的转换方的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。向。标识出初始状态和终止状态。l 状态转换矩阵状态转换矩阵 可用二维数组描述。标识出初始状态和终可用二维数组描述。标识出初始状态和终 止状态。若止状态。若DFA中有中有 f (SI, a)=SJ，则：，则： Trans (SI，a) SJl

25、对于对于 * *中的任何字符串中的任何字符串t,t,若存在一条从初若存在一条从初始结点到某一终止结点的路径，且这条路始结点到某一终止结点的路径，且这条路上所有弧的标记符连接成的字符串等于上所有弧的标记符连接成的字符串等于t,t,则称则称t t可为可为DFA MDFA M所所接受（识别）接受（识别）。lDFA M DFA M 所能接受的字符串的全体记为所能接受的字符串的全体记为L(M)L(M)称为称为M M所能接受（识别）的语言。所能接受（识别）的语言。nDFA接受的字符串接受的字符串l初始状态唯一。初始状态唯一。l转换函数转换函数f:Sf:SS S是一个单值函数，也就是一个单值函数，也就是说，

26、对任何状态是说，对任何状态s s S,S,和输入符号和输入符号 a a, , f(s,a) f(s,a) 唯一地确定了下一个状态。即转换唯一地确定了下一个状态。即转换函数至多确定一个状态。函数至多确定一个状态。l没有空边。即没有输入为没有空边。即没有输入为 （ ）nDFA的确定性的确定性u 是字母表是字母表u SSSS是状态集是状态集u S S0 0是初始状态集是初始状态集u f f是转换函数，但不要求是单值的是转换函数，但不要求是单值的 f: SS f: SS ( ( ) 2 2SSSSu TS TS是终止状态集是终止状态集l定义定义2 2：设设A A是一个是一个NFANFA，A= (A=

27、( ,SS,S,SS,S0 0,f,TS),f,TS)则定义则定义L(A)L(A)为从任意初始状态到任意终止状为从任意初始状态到任意终止状态所接受的字符串集合。态所接受的字符串集合。 L(A)= |s0 s, s0 S0 s TSnNFANFA的一个例子的一个例子SPZ00,1111n自动机等价自动机等价设设A1和和A2是同一个字母表上的自动机，如果是同一个字母表上的自动机，如果有有L(A1)=L(A2)，则称则称A1和和A2等价。等价。nNFA到到DFA的转换（确定化）的转换（确定化）对于每一个非确定自动机对于每一个非确定自动机A，存在一个确定，存在一个确定自动机自动机A，使得使得L(A)=

28、L(A)。n确定化算法确定化算法子集法子集法已知已知 NFA: A=( , S, f, S0, Z) 构造构造 DFA: A=( , S, f, S0, Z)1.令令A的初始状态为的初始状态为S0=S1,S2,Sk,其中其中S1Sk是是A的全部初始状态。的全部初始状态。2.若若S=S1,Sm是是A的一个状态，的一个状态，a则定义则定义f(S, a)=f(S1,a) f(S2,a) f(Sm,a)=Q 将将Q加入加入S，重复该过程，直到，重复该过程，直到S收敛。收敛。3.若若S=S1,Sn是是A的一个状态的一个状态,且存在一个且存在一个Si是是A的的终止状态，则令终止状态，则令S为为A的终止状态

29、。的终止状态。n带空边的带空边的NFA的确定化的确定化定义定义：设I是NFA的状态集的子集，则I的闭包为： _CLOSURE(I)=I q|f(p, )=q,p_CLOSURE(I)定义定义：设I是NFA状态集的子集，则Ia= _CLOSURE(J)，J=q|f(p,a)=q,p In确定化算法确定化算法子集法子集法已知已知 A A：NFA, NFA, 构造构造 A:DFAA:DFA1.1.令令A的初始状态为的初始状态为I0= _CLOSURE(S1,S2,Sk), 其中其中S1Sk是是A的全部初始状态。的全部初始状态。2.2.若若I=S1,Sm是是A的一个状态，的一个状态，a则定义则定义 f

30、(I, a)=Ia 将将Ia加入加入S，重复该过程，直到，重复该过程，直到S收敛。收敛。3.3.若若I=S1,Sn是是A的一个状态的一个状态, ,且存在一个且存在一个Si是是A A的终止状态，则令的终止状态，则令I为为A的终止状态。的终止状态。n带空边的带空边的NFA确定化的例子确定化的例子nDFA化简（极小化）化简（极小化）l 状态等价状态等价 对对DFA中的两个状态中的两个状态S1和和S2，如果将它们看作是初，如果将它们看作是初始状态，所接受的符号串相同，则定义始状态，所接受的符号串相同，则定义S1和和S2是等是等价的。价的。l无关状态无关状态从有限自动机的开始状态开始，任何输入序列都不从

31、有限自动机的开始状态开始，任何输入序列都不能到达的状态。能到达的状态。l最小最小DFADFA如果如果DFA中没有无关状态，也没有彼此等价的状态，中没有无关状态，也没有彼此等价的状态，则称该自动机是最小的。则称该自动机是最小的。nDFA化简算法化简算法-状态分离法状态分离法 1.1.将将DFA的所有状态的所有状态K K按终态和非终态划分成两个子集按终态和非终态划分成两个子集Z与与K-Z，构成初始化分，记作：，构成初始化分，记作： =Z, K-Z。 2.2.设当前的划分设当前的划分 中已经含有中已经含有m个子集个子集: =I1,I2,Im对于每一个子集对于每一个子集Ii=Si1,Si2,Sin及每

32、一个及每一个a，设，设Iin=f(Ii,a)=f(Si1,a) f(Si2,a) f(Sin,a)若若Iin中的状态分别落在中的状态分别落在 中中p个不同的子集，则将个不同的子集，则将Iin分分为为p个更小的子集，得到新的划分个更小的子集，得到新的划分 new。3. 若若 new , 则将则将 new作为作为 重复重复(2)，直到，直到 不能划分。不能划分。4. 将最后所得到的划分将最后所得到的划分 中的每个子集看成一个状态，中的每个子集看成一个状态，边作相应修改，确定开始状态和结束状态。边作相应修改，确定开始状态和结束状态。nririniaSfaIfI1),(),(nririniaSfaIf

33、I1),(),(nririniaSfaIfI1),(),(nDFA化简的例子化简的例子nDFA化简的例子化简的例子 aCDBAEFSbaaaaabbbbbabFl描述程序设计语言中单词的一种简单而描述程序设计语言中单词的一种简单而且数学化的工具。且数学化的工具。l表示符号串的构成模式表示符号串的构成模式l正则表达式正则表达式r r定义了一个符号串集合定义了一个符号串集合rs, rs, rsrs内的每个符号串都与内的每个符号串都与r r所定义的模式所定义的模式相匹配，相匹配，rsrs称为由称为由r r生成的语言生成的语言L(r)L(r)l正则表达式中出现的所有符号构成的集正则表达式中出现的所有符

34、号构成的集合为该正则表达式的字母表，用合为该正则表达式的字母表，用 表示表示 主要内容：主要内容：l基本概念基本概念l正则表达式定义及一些性质正则表达式定义及一些性质l扩充的正则表达式及程序设计语言中扩充的正则表达式及程序设计语言中单词的定义单词的定义l正则表达式与有限自动机等价正则表达式与有限自动机等价n正则表达式定义正则表达式定义l 为给定的字母表，则每个为给定的字母表，则每个 上的正则表达上的正则表达式将定义式将定义 上的一个字符串集。上的一个字符串集。 用用R R 表示表示 上的正则表达式上的正则表达式，用用L(RL(R ) )表示表示R R 所表示的字所表示的字符串集合符串集合 。即

35、：函数。即：函数L L表示正则表达式到字表示正则表达式到字符串集的映射。符串集的映射。l则则R R 的定义及其含义如下：的定义及其含义如下： u 是是 正则表达式，即正则表达式，即R R 。其中。其中L(L()= )= 。u 是正则表达式，即是正则表达式，即R R 。其中。其中L(L( )= )= 。u c c是正则表达式，即是正则表达式，即c c R R 。其中。其中L(c)=cL(c)=c。u A A和和B B是正则表达式，即是正则表达式，即A A R R ，B B R R ，则有，则有 ( A )( A ) R R ，L( (A) )L( (A) )= L(A)= L(A)A | BA

36、| B R R ，L( A | B )L( A | B )= L(A)= L(A) L(B)L(B)A BA B R R ，L( A B )L( A B )= L(A)L(B)= L(A)L(B)A A* * R R ，L( AL( A* *) )= L(A)= L(A)* * l正则表达式例正则表达式例l = a,b .= a,b . 正则表达式正则表达式e eabab* *2. a(a|b)2. a(a|b)* * L(e)L(e) 上所有以上所有以a a为首后跟任意多为首后跟任意多个（包括个（包括0 0个）个）b b的字符串集的字符串集1.1. 上所有以上所有以a a为首的字符串集为首的字符串集q A | B = B | AA | B = B | A | | 的可交换性的可交换性q A | (B | C) =(A | B ) CA | (B | C) =(A | B ) C | | 的可结合性的可结合性q A (B C) =(A B )CA (B C) =(A B )C 连接的可结合性连接的可结合性q A (B | C) =A B | A C A (B | C) =A B | A C 连接的可分配