形式语言与自动机理论--第四章(蒋宗礼)

形式语言与自动机理论FormalLanguagesandAutomataTheory蒋宗礼课程目的和基本要求•课程性质–技术基础•基础知识要求–数学分析（或者高等数学），离散数学•主要特点–抽象和形式化–理论证明和构造性–基本模型的建立与性质课程目的和基本要求•本专业人员4种基本的专业能力–计算思维能力–算法的设计与分析能力–程序设计和实现能力–计算机软硬件系统的认知、分析、设计与应用能力•计算思维能力–逻辑思维能力和抽象思维能力–构造模型对问题进行形式化描述–理解和处理形式模型课程目的和基本要求•知识–掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。•能力–培养学生的形式化描述和抽象思维能力。–使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。主要内容•语言的文法描述。•RL–RG、FA、RE、RL的性质。•CFL–CFG(CNF、GNF)、PDA、CFL的性质。•TM–基本TM、构造技术、TM的修改。•CSL–CSG、LBA。教材及主要参考书目1.蒋宗礼，姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003年2.JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,20013.JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979第4章正则表达式•正则文法擅长语言的产生，有穷状态自动机擅长语言的识别。•本章讨论正则语言的正则表达式描述。它在对正则语言的表达上具有特殊的优势，为正则语言的计算机处理提供了方便条件。–简洁、更接近语言的集合表示和语言的计算机表示等。第4章正则表达式•主要内容–典型RE的构造。–与RE等价FA的构造方法。–与DFA等价的RE的构造。•重点–RE的概念。–RE与DFA的等价性。•难点：RE与DFA的等价性证明。4.１启示产生语言{anbmck|n，m，k≥1}∪{aicnbxam|i≥0,n≥1,m≥2,x为d和e组成的串}的正则文法为AaA|aB|cEBbB|bCCcC|cEcE|bFFdF|eF|aHHaH|a4.１启示•接受此语言的NFAM4.１启示•计算集合set(q)set(A)={an|n≥0}={a}*set(B)=set(A){a}{bn|n≥0}={anabm|m，n≥0}={a}*{a}{b}*={a}+{b}*set(C)=set(B){b}{c}*={a}*{a}{b}*{b}{c}*={a}+{b}+{c}*set(D)=set(C){c}={a}+{b}+{c}*{c}={a}+{b}+{c}+4.１启示set(E)=set(A){c}{c}*={a}*{c}{c}*={a}*{c}+set(F)=set(E){b}{d，e}*={a}*{c}+{b}{d，e}*set(H)=set(F){a}{a}*={a}*{c}+{d，e}*{a}{a}*={a}*{c}+{d，e}*{a}+set(I)=set(H){a}={a}*{c}+{d，e}*{a}+{a}L(M)=set(D)∪set(H)={a}+{b}+{c}+∪{a}*{c}+{d，e}*{a}+{a}4.１启示根据集合运算的定义，{d，e}={d}∪{e}。从而，{d，e}*=({d}∪{e})*。这样可以将L(M)写成如下形式：L(M)={a}+{b}+{c}+∪{a}*{c}+({d}∪{e})*{a}+{a}记作：a+b+c++a*c+(d+e)*a+a=aa*bb*cc*+a*cc*(d+e)*aaa*4.2RE的形式定义•正则表达式(regularexpression，RE)⑴Φ是∑上的RE，它表示语言Φ；⑵ε是∑上的RE，它表示语言{ε}；⑶对于a∈∑，a是∑上的RE，它表示语言{a}；4.2RE的形式定义⑷如果r和s分别是∑上表示语言R和S的RE，则：r与s的“和”(r+s)是∑上的RE，(r+s)表达的语言为R∪S；r与s的“乘积”(rs)是∑上的RE，(rs)表达的语言为RS；r的克林闭包(r*)是∑上的RE，(r*)表达的语言为R*。⑸只有满足⑴、⑵、⑶、⑷的才是∑上的RE。4.2RE的形式定义•例4-1设∑={0，1}⑴0，表示语言{0}；⑵1，表示语言{1}；⑶(0+1)，表示语言{0，1}；⑷(01)，表示语言{01}；⑸((0+1)*)，表示语言{0，1}*；⑹((00)((00)*))，表示语言{00}{00}*；4.2RE的形式定义⑺((((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.2RE的形式定义•约定⑴r的正闭包r+表示r与(r*)的乘积以及(r*)与r的乘积：r+=(r(r*))=((r*)r)⑵闭包运算的优先级最高，乘运算的优先级次之，加运算“+”的优先级最低。所以，在意义明确时，可以省略其中某些括号。((((0+1)*)000)((0+1)*))=(0+1)*000(0+1)*4.2RE的形式定义((((0+1)*)(0+1))((0+1)*))=(0+1)*(0+1)(0+1)*⑶在意义明确时，REr表示的语言记为L(r)，也可以直接地记为r。⑷加、乘、闭包运算均执行左结合规则。4.2RE的形式定义•相等(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+tr4.2RE的形式定义⑶交换律：r+s=s+r。⑷幂等律：r+r=r。⑸加法运算零元素：r+Φ=r。⑹乘法运算单位元：rε=εr=r。⑺乘法运算零元素：rΦ=Φr=Φ。⑻L(Φ)=Φ。⑼L(ε)={ε}。⑽L(a)={a}。4.2RE的形式定义⑾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.2RE的形式定义⒆L(rn)=(L(r))n。⒇rnrm=rn+m。一般地，r+ε≠r，(rs)n≠rnsn，rs≠sr。•幂r是字母表∑上的RE，r的n次幂定义为⑴r0=ε。⑵rn=rn-1r。4.2RE的形式定义•例4-2设∑={0，1}00表示语言{00}；(0+1)*00(0+1)*表示所有的至少含两个连续0的0、1串组成的语言；(0+1)*1(0+1)9表示所有的倒数第10个字符为1的串组成的语言；4.2RE的形式定义L((0+1)*011)={x|x是以011结尾的0、1串}；L(0+1+2+)={0n1m2k|m，n，k≥1}；L(0*1*2*)={0n1m2k|m，n，k≥0}；L(1(0+1)*1+0(0+1)*0))={x|x的开头字符与尾字符相同}。4.3RE与FA等价•正则表达式r称为与FAM等价，如果L(r)=L(M)。•从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计算出所给FA的各个状态q对应的set(q)，并且最终得到相应的FA接受的语言的RE表示。•寻找一种比较“机械”的方法，使得计算机系统能够自动完成FA与RE之间的转换。4.3.1RE到FA的等价变换•0对应的FA•01对应的FA4.3.1RE到FA的等价变换•0+1对应的FA4.3.1RE到FA的等价变换•0*对应的FA4.3.1RE到FA的等价变换定理4-1RE表示的语言是RL。证明：•施归纳于正则表达式中所含的运算符的个数n，证明对于字母表∑上的任意正则表达式r，存在FAM，使得L(M)=L(r)。–M恰有一个终止状态。–M在终止状态下不作任何移动。4.3.1RE到FA的等价变换n=0r=εr=Φr=a4.3.1RE到FA的等价变换设结论对于n=k时成立，此时有如下FA：M1=(Q1，∑，δ1，q01，{f1})M2=(Q2，∑，δ2，q02，{f2})L(M1)=L(r1)，L(M2)=L(r2)。Q1∩Q2=Φ。n=k4.3.1RE到FA的等价变换n=k+1r=r1+r2取q0，fQ1∪Q2，令M=(Q1∪Q2∪{q0，f}，∑，δ，q0，{f})①δ(q0，ε)={q01，q02}；②对q∈Q1，a∈∑∪{ε}，δ(q，a)=δ1(q，a);对q∈Q2，a∈∑∪{ε}，δ(q，a)=δ2(q，a)；③δ(f1，ε)={f}；④δ(f2，ε)={f}。4.3.1RE到FA的等价变换n=k+1r=r1+r24.3.1RE到FA的等价变换•M=(Q1∪Q2，∑，δ，q01，{f2})•①对q∈Q1-{f1}，a∈∑∪{ε}–δ(q，a)=δ1(q，a)；•②对q∈Q2-{f2}，a∈∑∪{ε}–δ(q，a)=δ2(q，a)；•③δ(f1，ε)={q02}4.3.1RE到FA的等价变换r=r1r24.3.1RE到FA的等价变换•M=(Q1∪{q0，f}，∑，δ，q0，{f})•其中q0，fQ1，定义δ为①对q∈Q1-{f1}，a∈∑，δ(q，a)=δ1(q，a)。②δ(f1，ε)={q01，f}。③δ(q0，ε)={q01，f}。4.3.1RE到FA的等价变换r=r1*4.3.1RE到FA的等价变换•按照定理4-1证明给出的方法构造一个给定RE的等价FA时，该FA有可能含有许多的空移动。•可以按照自己对给定RE的“理解”以及对FA的“理解”“直接地”构造出一个比较“简单”的FA。•定理证明中所给的方法是机械的。由于“直接地”构造出的FA的正确性依赖于构造者的“理解”，所以它的正确性缺乏有力的保证。4.3.1RE到FA的等价变换•例4-3构造与(0+1)*0+(00)*等价的FA。4.3.1RE到FA的等价变换•按照对(0+1)*0+(00)*的“理解”“直接地”构造出的FA。4.3.2RL可以用RE表示•计算DFA的每个状态对应的集合——字母表的克林闭包的等价分类，是具有启发意义的。•这个计算过程难以“机械”地进行。•计算q1到q2的一类串的集合：Rkij。•图上作业法。4.3.2RL可以用RE表示定理4-2RL可以用RE表示。设DFAM=({q1，q2，…，qn}，∑，δ，q1，F)Rkij={x|δ(qi，x)=qj而且对于x的任意前缀y(y≠x，y≠ε)，如果δ(qi，y)=ql，则l≤k}。4.3.2RL可以用RE表示R0ij={a|δ(qi，a)=qj}如果i≠j{a|δ(qi，a)=qj}∪{ε}如果i=jRkij=Rk-1ik(Rk-1kk)*Rk-1kjRk-1ijFqnffRML1)(4.3.2RL可以用RE表示•图上作业法启示4.3.2RL可以用RE表示•图上作业法操作步骤⑴预处理：①用标记为X和Y的状态将M“括起来”：在状态转移图中增加标记为X和Y的状态，从标记为X的状态到标记为q0的状态引一条标记为ε的弧；从标记为q(q∈F)的状态到标记为Y的状态分别引一条标记为ε的弧。②去掉所有的不可达状态。4.3.2RL可以用RE表示⑵对通过步骤(1)处理所得到的状态转移图