1、形式语言与自动机理论山东大学计算机科学与技术学院2007.3第四章 正规表达式4.1 正规表达式的形式定义v 定义：设是一个字母表，字母表上正规式（Regular Expression,RE）和正规集定义如下：（1）是上的正规式，对应的正规集为；（2）是上的正规式，对应的正规集为；（3）对a，a是上的正规式，对应的正规 集为a；第四章 正规表达式4.1 正规表达式的形式定义（4）如果r和s分别是上的正规式，对应的正 规集为R和S。那么 (r+s)为正规式，对应的正规集为RS；(rs)为正规式，对应的正规集为RS；(r*)为正规式，对应的正规集为R*（5）只有满足上述形式定义的表达式才是上的正规
2、式，它所表达的语言是正规集。第四章 正规表达式v正规表达式的运算性质 假设r,s,t都是上正规式，则有以下性质：（1）结合律；（2）分配律；（3）交换律；（4）幂等律；（5）加运算单位元；（6）乘运算单位元；（7）乘运算零元；（8）(r*)*=r*；（9）r*=r+；（10）*=（11）*=4.1 正规表达式的形式定义第四章 正规表达式4.2 正规表达式与FA的等价 假设 r 是上的正规式，M 是一个 FA。若L(r)=L(M)，则称正规式 r 与 FA M 等价。第四章 正规表达式4.2 正规表达式与FA的等价定理：每个正规表达式 r 都存在一个-NFA M 使得L(M)=L(r)。(1)运
3、算符个数为0q0qfq0aq0qf第四章 正规表达式定理：每个正规表达式 r 都存在一个-NFA M 使得L(M)=L(r)。(2)运算符个数不为0 r=r1+r2M2M1q0f1q1f2q2f0第四章 正规表达式定理：每个正规表达式 r 都存在一个-NFA M 使得L(M)=L(r)。(2)运算符个数不为0 r=r1r2M2M1f1q1f2q2第四章 正规表达式定理：每个正规表达式 r 都存在一个-NFA M 使得L(M)=L(r)。(2)运算符个数不为0 r=r1*M1q0f1q1f0第四章 正规表达式4.2 正规表达式与FA的等价定理：设 L 是被 DFA M 接受的语言，则 L 可以被
4、正规表达式表示。-NFANFADFARGRE第五章 正规语言的性质5.1 Pumping 引理定理：假设 为有限字母表，L*。若 L 是正规语言，那么存在正整数 n 使得对任意的w1,w2,w3*,当w1w2w3L 并且|w2|n,可以写成 w2=,这里，|n.则 w1kw3L (k=0,1,2,.)。(1)Pumping 引理的提出第五章 正规语言的性质5.1 Pumping 引理(1)Pumping 引理的提出Pumping引理：假设 L是正规集，那么存在正整数 n 使得当 wL 并且|w|n,就可以写出 w=，这里，|n，且对k0,则 kL。第五章 正规语言的性质5.1 Pumping
5、引理(2)Pumping 引理的应用例1：证明 L1=anbn|n1不是RL。例2：证明 L2=w|w*且=0,1,w=w-1 不是 RL。这里w是回文。即w与w的逆 相同。第五章 正规语言的性质5.1 Pumping 引理(2)Pumping 引理的应用例3：证明 L3=an2|nN不是RL。例4：证明 L4=ap|p是素数不是 RL。第五章 正规语言的性质5.2 正规语言的封闭性(1)正规语言在并、乘积、闭包运算下是封 闭的；(2)正规语言类在补运算下是封闭的；(3)正规语言类在交运算下是封闭的；第五章 正规语言的性质5.2 正规语言的封闭性(4)代换定义：设，是两个字母表，映射 f:p(
6、*)称为到的代换。如果对a,f(a)是上的RL，则称f是 正则代换或正规代换。正规语言类在代换下是封闭的。第五章 正规语言的性质(5)同态5.2 正规语言的封闭性定义：设，是两个字母表，映射 f:*如果对x,y*,有f(xy)=f(x)f(y)，则称f是从到*的同态映射。正规语言在同态和逆同态下是封闭的。第五章 正规语言的性质5.2 正规语言的封闭性正规语言在商运算下是封闭的。定义：假设L1,L2*,则L1和L2的商定义 为：L1/L2=x|yL2，使得xyL1第五章 正规语言的性质5.3 Myhill-Nerode定理和 DFA 极小化一、相关概念1、等价关系2、划分3、划分加细4、等价类5
7、、商集6、等价关系的指数第五章 正规语言的性质5.3 Myhill-Nerode定理和 DFA 极小化二、Myhill-Nerode定理 定理：假设是有限字母表，L *,以下三个命题等价：（1）L是正规语言；（2）L是*上具有有穷指数的右不变等价关系的某些等价类的并；（3）如果 RL=|x,y*,对z*,xzL当且仅当yzL，则RL的指数有穷。第五章 正规语言的性质5.3 Myhill-Nerode定理和 DFA 极小化 例：假设 L=0*10*它被下列自动机接受。能否简化？q0q1q2q3q4q500110110100,1q0:(00)nR(00)mq1:0(00)nR(00)m0q2:(0
8、0)n1R(00)m1q3:(00)n01R(00)m01q4:(0)n10(0)mR(0)p10(0)qq5:xRmy,x和y至少含有两个1的串。(这里m,n,p,q 0)第五章 正规语言的性质5.3 Myhill-Nerode定理和 DFA 极小化二、Myhill-Nerode定理推论 1：对任意正规语言 L，如果DFA M满足L(M)=L，则|*/RL|Q|推论 2：在同构（即状态重新命名）的意义下，接受一个语言 L 的最小DFA是唯一的。第五章 正规语言的性质5.3 Myhill-Nerode定理和 DFA 极小化三、DFA的极小化 1、状态等价和可区分 设 DFA M=(Q,q0,F
9、)，如果x*，使得 Q中的两个状态q1,q2，(q1,x)F 和(q2,x)F中仅有一个成立，则称q1和q2是可区分的。若对不同的状态q1,q2和任意的串 x*，有(q1,x)F当且仅当(q2,x)F。则称q1和q2是等价的，记为q1q2。第五章 正规语言的性质5.3 Myhill-Nerode定理和 DFA 极小化三、DFA的极小化 2、利用等价和可区分概念，标记填表求极小化（1）构造一个二维表（2）标识可区分状态（3）对剩余的每对状态进行标识（4）重复（3）直到所有状态对处理完毕。第五章 正规语言的性质例：设DFA M=(q0,q1,.,q5,0,1,q0,F)q2q0q1q4q3q5010100111100第五章 正规语言的性质5.3 Myhill-Nerode定理和 DFA 极小化四、正规语言的判定算法1、空性、有穷性、无穷性定理：具有 n 个状态的有限自动机接受的串集合是：（1）非空的 当且仅当这个有限自动机接受一个长度小于 n 的串，即*，|n，且(q0,)F；（2）无穷的 当且仅当这个有限自动机接受某些长度为 l 的串，这里 nl 2n。第五章 正规语言的性质5.3 Myhill-Nerode定理和 DFA 极小化四、正规语言的判定算法2、等价性定理：存在一个算法，它能判断两个FA 是否等价。
