形式语言与自动机理论第四章(蒋宗礼)ppt课件.ppt
形式语言与自动机理论Formal Languages and Automata Theory,蒋宗礼,课程目的和基本要求,课程性质技术基础 基础知识要求 数学分析（或者高等数学），离散数学 主要特点 抽象和形式化 理论证明和构造性 基本模型的建立与性质,课程目的和基本要求,本专业人员4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述理解和处理形式模型,课程目的和基本要求,知识掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。能力培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。,主要内容,语言的文法描述。RLRG、 FA、RE、RL的性质 。CFLCFG(CNF、GNF)、PDA、CFL的性质。 TM基本TM、构造技术、TM的修改。CSLCSG、LBA。,教材及主要参考书目,蒋宗礼，姜守旭. 形式语言与自动机理论. 北京：清华大学出版社，2003年 John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001 John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979,第4章 正则表达式,正则文法擅长语言的产生，有穷状态自动机擅长语言的识别。本章讨论正则语言的正则表达式描述。它在对正则语言的表达上具有特殊的优势，为正则语言的计算机处理提供了方便条件。简洁、更接近语言的集合表示和语言的计算机表示等。,第4章 正则表达式,主要内容典型RE的构造。与RE等价FA的构造方法。与DFA等价的RE的构造。重点RE的概念。RE与DFA的等价性。难点：RE与DFA的等价性证明。,4. 启示,产生语言anbmck|n，m，k1aicnbxam|i0,n1,m2,x为d和e组成的串 的正则文法为AaA|aB|cEBbB|bCCcC|cE cE|bFFdF|eF|aHHaH|a,4. 启示,接受此语言的NFA M,4. 启示,计算集合 set(q)set(A)=an|n0=a* set(B)= set(A)abn|n0 =anabm|m，n0 =a*ab*=a+b*set(C)= set(B)bc* =a*ab*bc*=a+b+c*set(D)= set(C) c=a+b+c*c =a+b+c+,4. 启示,set(E)= set(A)cc* =a*cc*=a*c+set(F)= set(E)bd，e*=a*c+bd，e*set(H)= set(F)aa*=a*c+d，e*aa* =a*c+d，e*a+set(I)= set(H)a=a*c+d，e*a+aL(M)= set(D)set(H) = a+b+c+a*c+d，e*a+a,4. 启示,根据集合运算的定义，d，e=de。从而，d，e*=(de)*。这样可以将L(M)写成如下形式：L(M)= a+b+c+a*c+(de)*a+a 记作：a+b+c+a*c+(d+e)*a+a= aa*bb*cc*+a*cc*(d+e)* aaa*,4.2 RE的形式定义,正则表达式(regular expression，RE) 是上的RE，它表示语言； 是上的RE，它表示语言； 对于a，a是上的RE，它表示语言a；,4.2 RE的形式定义, 如果r和s分别是上表示语言R和S的RE，则： r与s的“和” (r+s)是上的RE，(r+s)表达的语言为RS； r与s的“乘积” (rs)是上的RE，(rs)表达的语言为RS； r的克林闭包(r*)是上的RE，(r*)表达的语言为R*。 只有满足、的才是上的RE。,4.2 RE的形式定义,例 4-1 设=0，1 0，表示语言0； 1，表示语言1； (0+1)，表示语言0，1； (01)，表示语言01； (0+1)*)，表示语言0，1*； (00)(00)*)，表示语言0000*；,4.2 RE的形式定义, (0+1)*)(0+1)(0+1)*)，表示语言0，1+； (0+1)*)000)(0+1)*)，表示0，1上的至少含有3个连续0的串组成的语言； (0+1)*)0)1)，表示所有以01结尾的0、1字符串组成的语言； (1(0+1)*)0)，表示所有以1开头，并且以0结尾的0、1字符串组成的语言。,4.2 RE的形式定义,约定 r的正闭包r+表示r与(r*)的乘积以及(r*)与r的乘积： r+=(r(r*)=(r*)r) 闭包运算的优先级最高，乘运算的优先级次之，加运算“+”的优先级最低。所以，在意义明确时，可以省略其中某些括号。 (0+1)*)000)(0+1)*)=(0+1)*000(0+1)*,4.2 RE的形式定义,(0+1)*)(0+1)(0+1)*)=(0+1)*(0+1)(0+1)* 在意义明确时，RE r表示的语言记为L(r)，也可以直接地记为r。 加、乘、闭包运算均执行左结合规则。,4.2 RE的形式定义,相等(equivalence)r、s是字母表上的一个RE，如果L(r)=L(s)，则称r与s相等，记作r=s 。相等也称为等价。几个基本结论 结合律：(rs)t=r(st) (r+s)+t=r+(s+t) 分配律：r(s+t)=rs+rt (s+t)r=sr+tr,4.2 RE的形式定义, 交换律：r+s=s+r。 幂等律：r+r=r。 加法运算零元素：r+=r。 乘法运算单位元：r=r=r。 乘法运算零元素：r=r=。 L()=。 L()=。 L(a)=a。,4.2 RE的形式定义, L(rs)=L(r)L(s)。 L(r+s)=L(r)L(s)。 L(r*)=(L(r)* 。 L(*)=。 L(r+)*)=L(r*)。 L(r*)*)=L(r*)。 L(r*s*)*)=L(r+s)*)。 如果L(r) L(s)，则r+s=s。,4.2 RE的形式定义, L(rn)=(L(r)n 。 rnrm=rn+m 。一般地， r+r，(rs)n rnsn，rssr。幂 r是字母表上的RE，r的n次幂定义为 r0=。 rn=rn-1r。,4.2 RE的形式定义,例 4-2 设=0，100表示语言00；(0+1)*00(0+1)*表示所有的至少含两个连续0的0、1串组成的语言；(0+1)*1(0+1)9表示所有的倒数第10个字符为1的串组成的语言；,4.2 RE的形式定义,L(0+1)*011)=x|x是以011结尾的0、1串；L(0+1+2+)=0n1m2k|m，n，k1；L(0*1*2*)=0n1m2k|m，n，k0；L(1(0+1)*1+0(0+1)*0)=x|x的开头字符与尾字符相同。,4.3 RE与FA等价,正则表达式r称为与FA M等价，如果L(r)=L(M)。从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计算出所给FA的各个状态q对应的set(q)，并且最终得到相应的FA接受的语言的RE表示。 寻找一种比较“机械”的方法，使得计算机系统能够自动完成FA与RE之间的转换。,4.3.1 RE到FA的等价变换,0对应的FA,01对应的FA,4.3.1 RE到FA的等价变换,0+1对应的FA,4.3.1 RE到FA的等价变换,0*对应的FA,4.3.1 RE到FA的等价变换,定理 4-1 RE表示的语言是RL。证明：施归纳于正则表达式中所含的运算符的个数n，证明对于字母表上的任意正则表达式r，存在FA M，使得L(M) = L(r) 。M恰有一个终止状态。M在终止状态下不作任何移动。,4.3.1 RE到FA的等价变换,n=0,r=,r=,r=a,4.3.1 RE到FA的等价变换,设结论对于n=k时成立，此时有如下FA：M1=(Q1，1，q01，f1)M2=(Q2，2，q02，f2)L(M1)=L(r1)，L(M2)=L(r2) 。Q1Q2=。,n=k,4.3.1 RE到FA的等价变换,n=k+1,r=r1+r2,取q0，fQ1Q2，令M=(Q1Q2q0，f，q0，f) (q0，)=q01，q02； 对qQ1，a，(q，a)=1(q，a); 对qQ2，a，(q，a)=2(q，a)； (f1，)=f； (f2，)=f。,4.3.1 RE到FA的等价变换,n=k+1,r=r1+r2,4.3.1 RE到FA的等价变换,M=(Q1Q2，q01，f2) 对qQ1-f1，a(q，a)=1(q，a)；对qQ2-f2，a(q，a)=2(q，a)； (f1，)=q02,4.3.1 RE到FA的等价变换,r=r1r2,4.3.1 RE到FA的等价变换,M=(Q1q0，f，q0，f)其中q0，fQ1，定义为 对qQ1-f1，a，(q，a)=1(q，a)。 (f1，)=q01，f。 (q0，)=q01，f。,4.3.1 RE到FA的等价变换,r=r1*,4.3.1 RE到FA的等价变换,按照定理4-1证明给出的方法构造一个给定RE的等价FA时，该FA有可能含有许多的空移动。可以按照自己对给定RE的“理解”以及对FA的 “理解” “直接地”构造出一个比较“简单”的FA。定理证明中所给的方法是机械的。由于“直接地”构造出的FA的正确性依赖于构造者的“理解”，所以它的正确性缺乏有力的保证。,4.3.1 RE到FA的等价变换,例 4-3 构造与 (0+1)*0+(00)*等价的FA。,4.3.1 RE到FA的等价变换,按照对(0+1)*0+(00)*的“理解” “直接地”构造出的FA。,4.3.2 RL可以用RE表示,计算DFA的每个状态对应的集合字母表的克林闭包的等价分类，是具有启发意义的。 这个计算过程难以“机械”地进行。 计算q1到q2的一类串的集合：Rkij 。图上作业法。,4.3.2 RL可以用RE表示,定理4-2 RL可以用RE表示。设DFA M=(q1，q2，qn，q1，F)Rkij=x|(qi，x)=qj而且对于x的任意前缀y(yx，y)，如果(qi，y)=ql，则lk。,4.3.2 RL可以用RE表示,R0ij=,a|(qi，a)=qj如果ij,a|(qi，a)=qj如果i=j,Rkij= Rk-1ik( Rk-1kk)* Rk-1kj Rk-1ij,4.3.2 RL可以用RE表示,图上作业法 启示,4.3.2 RL可以用RE表示,图上作业法操作步骤 预处理： 用标记为X和Y的状态将M“括起来”： 在状态转移图中增加标记为X和Y的状态，从标记为X的状态到标记为q0的状态引一条标记为的弧；从标记为q(qF)的状态到标记为Y的状态分别引一条标记为的弧。 去掉所有的不可达状态。,4.3.2 RL可以用RE表示, 对通过步骤(1)处理所得到的状态转移图重复如下操作，直到该图中不再包含除了标记为X和Y外的其他状态，并且这两个状态之间最多只有一条弧。 并弧 将从q到p的标记为r1，r2，rg并行弧用从q到p的、标记为r1+r2+rg的弧取代这g个并行弧。,4.3.2 RL可以用RE表示,去状态1如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，不存在从状态p到状态p的弧，将状态p和与之关联的这两条弧去掉，用一条从q到t的标记为r1r2的弧代替。 去状态2如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，从状态p到状态p标记为r3的弧，将状态p和与之关联的这三条弧去掉，用一条从q到t的标记为r1r3*r2的弧代替。,4.3.2 RL可以用RE表示,去状态3如果图中只有三个状态，而且不存在从标记为X的状态到达标记为Y的状态的路，则将除标记为X的状态和标记为Y的状态之外的第3个状态及其相关的弧全部删除。,4.3.2 RL可以用RE表示, 从标记为X的状态到标记为Y的状态的弧的标记为所求的正则表达式。如果此弧不存在，则所求的正则表达式为。,4.3.2 RL可以用RE表示,例 4-4 求图4-14所示的DFA等价的RE 。,4.3.2 RL可以用RE表示,预处理。,4.3.2 RL可以用RE表示,去掉状态q3。,4.3.2 RL可以用RE表示,去掉状态q4。,4.3.2 RL可以用RE表示,合并从标记为q2的状态到标记为Y的状态的两条并行弧。,4.3.2 RL可以用RE表示,去掉状态q0。,4.3.2 RL可以用RE表示,并弧。,4.3.2 RL可以用RE表示,去掉状态q1。,4.3.2 RL可以用RE表示,去掉状态q2。,1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)(00*+00*1)就是所求。,4.3.2 RL可以用RE表示,几点值得注意的问题 如果去状态的顺序不一样，则得到的RE可能在形式是不一样，但它们都是等价的。 当DFA的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。此时，相应的RE为。 不计算自身到自身的弧，如果状态q的入度为n，出度为m，则将状态q及其相关的弧去掉之后，需要添加n*m条新弧。,4.3.2 RL可以用RE表示, 对操作的步数施归纳，可以证明它的正确性。推论4-1 正则表达式与FA、正则文法等价，是正则语言的表示模型。,4.4 正则语言等价模型的总结,4.5 小结,本章讨论了RL及其与FA的等价性。 字母表上的RE用来表示上的RL。、a（a），是上的最基本的RE，它们分别表示语言、a，以此为基础，如果r和s分别是上的表示语言R和S的RE，则r+s、rs 、r*分别是上的表示语言RS、RS、 R*的RE。如果L(r)=L(s)，则称r与s等价。,4.5 小结, RE对乘、加满足结合律；乘对加满足左、右分配律；加满足交换率和幂等率；是加运算的零元素；是乘运算的单位元；是乘运算的零元素。 RE是RL的一种描述。容易根据RE构造出与它等价的FA。反过来，可以用图上作业法构造出与给定的DFA等价的RE。 RL的5种等价描述模型转换图。,
