还剩15页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
1.形式化2形式语言3数理逻辑4理论计算机科学理论计算机科学是关于计算、算法、程序和计算机的数学理论有许多分支,包括计算理论、.形式语言理论、形式语义理论,等等2将下列NFA转化为等价的DFAo据此画出状态转移图如下:证明设M,N分别是接受A和B的两个DFA证毕
2.正规语言的泵引理定理
2.1设£是正规语言,则存在一个常数匕对L中任何长度不小于攵的串卬,存在x,yz,使得川二肛z且
1.\xy\k,
2.\y\h
3.Vz
0.xyz GL.证明设M是接受L的DFA,有k个状态设卬=[〃2・•・〃££,其中吟k则M从开始状态处理完W共经历n+1个状态,分别记为外,名,・・・,外注意到n+lNk+1因为M只有k个不同的状态,所以在这n+1个状态中的前k+1个状态中一定有一个两个状态是相同的令这两个状态为么其中0rsk-l.因此上述处理w的计算路径被这两个状态分割成三段,从左向右数,第1段是从qo开始到q「结束,第2段从年开始到令结束,第3段从q,开始到小结束我们把这三段路径上处理的串分别记为x,yf zo从而易知x,y满足定理中的性质1和2而对于任何立0,串盯弓在M中可以先经过第1段计算路径处理完x,然后用连续i次第2段路径处理N最后用第3段路径处理z,最后停止在终止状态如因此,M接受X/Z,从而xyz GL o□注泵引理中的常数攵称为泵常数例
2.2令1={限9|1仑1}用泵引理证明L不是正规语言证明用反证法假设L是正规语言则L有一个泵常数匕取w二aWt根据泵引理,存在x,y,z使得w=xyz,其中|xy|Wk,卜巨1且xzeL.由|xy|gk可知y不含b,由|y|Nl可知y至少含一个因此xz中的a的个数小于k且b的个数等于ko由此可得xz不在L中矛盾口例
2.3令L={a jbj|访}o用泵引理证明L不是正规语言证明假设L是正规语言则L有一个泵常数k取VV=根据泵引理,存在x,y,z使得w=xyz,其中|孙|〈人W21且Vi
21.工/Z WL.易知y中至少含一个a且不含b,所以xy,Z中a的个数为k!+i・ln,其中〃二|yl令左!+«—1〃=左+1!1则.k,k!、i=-------+
1.n由于/刍必,所以〃整除0,从而i是整数对于这个整数i,等式1成立从而xyz中的个数为什1!,与其中b的个数相同这表明孙‘Z不在L中矛盾口例
2.4令L={a«|n是素数}用泵引理证明L不是正规语言证明练习
2.5令L={卬卬|we{O,l}+}o用泵引理证明L不是正规语言
1.Moore机在有限自动机的状态上添加输出动作,当自动机进入某个状态时,就输出该状态所对应的字符因此Moore机是在状态中输出的,当前的输出符号完全由当前的状态所确定定义
1.1Moore机是一个六元组M=,£,△»源,%其中Q是有限状态集,q是初始状态,2和△分别是输入和输出符号表,6是状态转移函数,8是状态-输出函数,它们分别为如下映射例
1.2构造一个Moore机,对于输入的任何二进制自然数x,输出xmod3分析我们为Moore机设置3个状态,分别表示模3运算的3个结果,即0,1和
2.我们让Moore机从左向右扫描二进制输入串,若当前扫描过的输入串模3的结果为i,则进入状态i,并输出i当扫描完整个输入串时,最后到达的状态将输出所需要的计算结果构造令Q二{0,1,2},2二{0,1},△={0,1,2,状态转移函数和状态-输出函数如下图所示分010,1—1,
2122.Mealy机在有限自动机的每个状态转移上添加输出动作,当自动机进行某个状态转移时,输出该转移所对应的字符,这种带输出的有限自动机称为Mealy机其形式定义请读者尝试写出来例2」下列Mealy机的功能是模拟二进制加法,处理的次序是从低位到高位该自动机使用两个状态,状态进行不带进位的加法,状态1进行带进位的加法由于Mealy机仅有一条输入带,所以这两个加项需要编码为一条输入串这里采用的编码方法是,从两个加数的低位开始,将对应数位上的两个数字编码为一个符号,即0,0,0,1,1,0或者1』最后添加0,0结束例如,我们将1和11编码为1,10,10,0,则下列Mealy机输出001,反过来就是相加的结果100,即十进制的4o请读者尝试该Mealy机模拟1+2和2+50,0/(0,1),(1,0)Q°)/(0,1),(1,0)/定理
2.2Moore机与Mealy机是等价的证明方法模拟法,即用两种自动机相互模拟对方的功能证明1)设M是一个Moore机,构造一个Mealy机模拟M推迟输出将状态的输出转移到该状态的出转移上2)设M是一个Mealy机,构造一个Moore机模拟M拆分状态对于M的任何状态q和其入转移上的输出符号x,用[q,x]作为Moore机的状态,负责输出x□
3.有限自动机的实现一个简单的实现方法如下第1步确定该DFA的语义
(1)确定其输入与输出方式;
(2)确定程序中会用到的主要数据结构;
(3)确定各状态与转移下的读取、存储,输出、返回等分析动作;第2步编写和调试程序
(1)编写程序的主体部分,其中每个状态分别用一个语句标号表示,下一状态的选择用条件控制语句实现,状态之间的转移用got语句实现
(2)添加头文件和变量声明语句有限自动机和正规表达式表示语言的能力是很有限的,只能表示正规语言根据Myhill-Nerode定理,正规语言的等价类是有限多的,而一些很简单的语言也会有无限多的等价类,例如{0叮521}本讲将介绍一种新的语言模型,称为上下文无关文法它是美国语言学家乔姆斯基(Chomsky)1956年提出的一种语法形式,乔姆斯基称之为转换生成文法(transformational-generativegrammar)o
1.概念语言是由语句构成的,语句是由字符构成的在乔姆斯基的文法中,把构成语句的字符称为终极符号,此外用若干变元分别指代某一类型的短语,这些变元也称为非终极符号,其中指代句子的变元称为文法的开始符终极符号和变元合称文法符号,它们可以组成各种句型上下无关文法用如下形式的表达式定义变元所指代的短语类型A fa其中A是非终极符号,a是文法符号串,描述了A类短语的结构这种表达式称为产生式定义一个变元可能需要多个产生式假设变元A有如下两条产生式A faAT B我们可以把它们合写为一条复合产生式A f其中a和0分别称为该复合产生式的候选式candidanto下面我们给出上下文无关文法的形式定义定义
1.1上下文无关文法context-free grammar,CFG是如下形式的四元组G=VN,VT,P,S其中VN和VT是两个字符表,其中的字符分别称为非终极符号non-terminal和终极符号terminal,S是VN中一个特殊的非终极符号,称为开始符号start symbol,P是产生式集合,其中的产生式production是形如A-a的表达式,其中A是非终极符号,a是文法符号串或者空串为了指明开始符为S,我们将文法名字写成G[S]在下面的例子中,我们一般用大写字母表示非终极符,小写字母表示终极符,第1条产生式的左部变元默认为开始符因此,给出一个文法时,无需再指出这些符号,只需列出所有产生式即可
2.文法所生成的语言我们讨论如何根据给定的上下无关文法来确定它所定义的语言我们可以把产生式的右部视为带变元的正规表达式,其中有语言之间的连接、并和星闭包等3种正规运算一个变元的复合产生式的右部定义了该变元所指代的终极符号串集合定义
2.1文法变元A所指代的语言记为LA,终极符号a所指代的语言定义为La尸{a},空串所指代的语言定义为Lg={£},对于任何文法符号串a和团定义更一般地,对于由多个文法符号串并联而成的串,其指代的语言定义为这些文法符号串所指代语言的并集对于文法变元A,若A的所有产生式为人―||/・・・|〃,则定义“A=au〃%U・・・U〃4定义
2.2在文法G[S]中,开始符所指代的语言LS称为为文法G所生成的语言,另记为LG,其中的字符串称为该文法所生成的句子例
2.3根据上述定义
2.1和
2.2中的规定,我们来尝试确定例
1.4中文法Gi所生成的语言根据该文法,我们得如下方程组L⑻=LALB LA=LnA\JUn=A U{〃}LB=LVBUMV=vLB U{v}由第2个方程可求得£A={n z|/l}用归纳法不难证明上述结果是正确的同理,由第3个方程可求得£B={v z|zl}再由第1个方程立刻可得LS=|51}这就是Gi所生成的语言顺便说一下,如果我们把文法Gi中的终极符号n和v分别理解为名词和动词,则根据A的产生式,A可理解为由名词组成的名词短语,根据B的产生式,B可理解为由动词组成的动词短语,从而根据S的产生式可知S所指代的语句是由名词短语连接动词短语所组成的
3.推导在乔姆斯基的文法理论中,把产生式用作推导规则derivation rule,可以开始符出发推出文法所生成的任何句子因此,我们把产生式A-a理解为A可推出a,或者A可重写为a,或者a可代入A,所以产生式也称为重写规则rewrite rule或者变元代入规则subsituation rule定义
2.1设G是上下文无关文法,若存在产生式A-a,则对于任何符号串u和v,有uAv=uav称为从串uAv到uav的一步推导derivation对于任何文法符号串x和y,若x=y或者x经过若干步推导可产生y,则称x推导或者生成y,记为x=*y例
2.2在例
1.4的文法Gi中,从A出发推导nnn,从B出发推导vvv,从S出发推导nnvv A=nA=nnA=nnn B=vB=vvB=vvv S=AB=nAB=nnB=nnvB=nnvv习惯上我们总是对于当前字符串中最左边的变元进行推导,这称为最左推导left-most derivationo今后,在没有说明的情况下,所说的推导默认为最左推导上述推导过程需要重复写出已推出的字符,比较麻烦,更简便的方式是用推导树记录推导过程定义
2.3推导树以变元为根和内结点,从一个变元推导出的字符从左到右分别是该结点的子结点,所有树叶从左到右构成所推导的串例
4.2A^0A|O AfiA|1该文法所生成的语言是0|1+,即所有非空的二元串练习
4.3为下列正规语言设计上下文无关文法1含偶数个0的二元串2长度为偶数的二元串从上面的例子和练习,读者可以看到用递归产生式可以实现语言的星闭包运算下面我们将看到,用递归产生式还可以生成左右匹配的串,即语句内部的对称结构例如下列语言中的语句都具有某种对称结构L]={0T|〃21}L2=1WW RI WG{0,1}+}这些语言分别由下列文法生成G:S f0Sl|01G2:S^0S0|lSl|00|ll我们知道,这些语言都不是正规语言,不能用正规表达式或者有限自动机进行定义因此,上下文无关文法的语言描述能力是比较强的,其秘密就在于递归产生式,可以生成左右匹配的字符串
4.歧义文法从推导树看句子的短语结构1句子由短语组成,短语之间有两种关系即结合关系和构成关系结合关系是指若干相邻短语之间结合在一起构成上层短语;构成关系是指一个短语是另一个短语的成分2根据推导树可以看出所推出的句子的短语结构,即识别出该句子的所有短语及其之间的结合关系和构成关系因此,推导树也称为语法分析树parsing tree语法分析在程序编译技术中,需要对源程序进行语法分析,其主要目的是构造源程序的语法分析树有一类方法是从根开始往下构造语法分析树,这种构造方法称为自上而下的语法分析,其实质是为源程序构造最左推导定理
5.1推导树与最左推导是一一对应的证明用归纳法可证明,由最左推导只能构造出唯一的推导树,而由推导树也只能构造出唯一的最左推导因此,二者是一一对应的句子的语法结构是其语义的决定因素之一不同的语法结构往往导致不同的语义定义
5.2若在某文法下一个字符串有两个不同的最左推导,则该文法是歧义的ambiguous例
5.3在下列文法G[E]中,i+i*i有两个不同的最左推导,所以是歧义文法E—E+E|E*E IE Ii根据第1个推导树分析得的语法结构,i+i*i应解释为先做加法然后做乘法;而第2个推导树所确定的语法结构则表明,应先做后面的乘法再做前面的加法因此,根据该文法无法确定一个正确的语义例
5.4例
5.3中的歧义文法可改写为如下非歧义性文法E-E+T|T T—T*F|F F-E|i定理
5.6上下文无关文法的歧义性是不可判定的定理
5.7上下文无关语言的固有歧义性是不可判定的
1.正规表达式转化为带空转移的NFA定义
2.1我们用正规表达式标记有限自动机中的转移,表示该转移可以处理该正规表达式所表示的任何输入串,这种有限自动机称为广义有限自动机,简称GFA GFA拆分法将正规表达式转化为等价的LNFA
2.将有限自动机转化为正规表达式GFA去状态法第1步去掉陷阱状态第2步添加两端状态在自动机转移图的两端添加一个新的开始状态X和一个新的接受状态Y,让X空转移到原来的开始状态,并且让原来所有接受状态空转移到Yo第3步合并转移合并两个状态之间的所有方向相同的转移为一个转移,其标记为所有被合并的转移上的标记的并如下图所示第4步挖去内部状态去掉一个内部状态,将该状态的每个入转移与每个出转移分别连接为一个转移m个入转移与n个出转移相互连接后形成mn个新转移设一对入转移和出转移上所标记的正规表达式分别为w和v,则连接后新转移上的标记如下定义若被去掉的状态上没有指向自己的转移,该标记为WV;若被去掉的状态上有一个标记为r的环,则该标记为wr、如下图所示第5步重复第3步和第4步,直到只剩下状态X到和Y以及二者间的一条转移,则该转移上的正规表达式就是所要求的结果3,将带空转移NFA转化为DFA的方法定义
4.1空转移闭包或£.闭包对于带空转移的NFA来说,其某个状态q的空转移闭包,记为£-Oosureq,是由该状态自身,以及该NFA从此状态出发,经过若干次空转移后,所能到达的所有状态构成的集合根据定义不难计算空转移闭包我们可以在状态转移图上,跟踪空转移,标记出所有空转移所到达的状态,然后将这些被标记的状态一一添加到所要求的闭包中即可状态子集闭包法将s-NFA转化为等价DFA,按如下3步构造该DFA的转移矩阵第1步,算出e-NFA的开始状态的£-闭包,作为DFA的开始状态第2步,为每个DFA状态构造后继状态令R为DFA的一个状态,a是一个输入符号我们构造R的a-转移后继状态S如下S=6--Closured^|3p GR.q G5〃,〃}即,若H某状态p经过a转移可到达状态q,则将q添加到S中,当没有状态可以添加时,再对S求空转移闭包此时所得的S就是R的a—转移后继状态第3步,将含NFA接受状态的DFA状态都指定为接受状态第6讲米希尔-奈罗德定理与DFA最小化一个正规语言的DFA是无穷多的,其中状态数最小的称为最小DFAo在实际应用中,作为一种算法,DFA当然是越小越好本讲讨论如何将一个DFA等价变换为最小DFAo这个等价变换的理论基础是米希尔-奈罗德定理
3.等价类相互等价的所有元素构成的集合称为一个等价类元素x所在的等价类记为[x]注意,[x]与[y]要么相等要么不相交n
4.集合的划分:设{4H<,<是A的一组子集若4•互不相交且A=u a,则称{a।Z=1是A的一个划分partition命题
1.设R是A上的一个等价关系,则R的所有等价类构成A的一个划分命题
2.设口是集合A的一个划分定义A上二元关系An如下xRny当且仅当存在4£II,X,y£4则心是等价关系推论
3.一个集合上的等价关系与该集合的划分是一一对应的
1.字符串集合上的两个等价关系我们先回顾一个定义,即有限自动机的状态所接受的语言设M是一个有限自动机,“是其状态若M从开始状态出发处理完串x后恰好到达状态外则称q接受底夕接受的所有串构成q所接受的语言,记为q°若M是DFA,则M可以确定地处理完任何串并且到达某个唯一状态,所以M的不同状态所接受的语言是不相交的因此,DFA各状态所接受的语言构成了输入串集合的划分这个划分定义了一个等价关系若两个输入串被DFA的同一个状态所接受,则称这两个串在该有限自动机下是等价的x定义
1.2设/是一个DFA,其输入符号表为Z我们在输入串集合Z*上定义二元关系RM如下RM={%被M的同一个状态所接受}显然RM是2上的等价关系,称之为M中的等价关系equivalence inM定义
1.3设L是一个语言,其符号表为E我们在Z*上定义二元关系如下,R广{x,y|X/zxz£L=yz£“读者不难验证是E*上的等价关系,我们称之为关于L的等价关系equivalence towardLo也许更文艺点,可称之为“走向L的等价关系”我们可以这样来理解该等价关系令x为一个串,则任何串z作为后缀连接到x上只能导致两个结果,即要么xz在L中要么xz不在L中前者将x带到了L中,后者将x带到了L外反过来,我们看到所有串Z被X划分为两类,即{ZEEIXZEL}和{Z£f IxzeL}前者可以视为X的正确向导集,后者为x的错误向导集因此,当且仅当两个串的正确向导集相同时才是关于L等价的引理
1.4设L是正规语言,M是接受L的DFA,则RM C,从而L的等价类数小于等于M的状态数证明设L的字母表为2,以下所讨论的串都是该字母表上的串设羽》£氏加,则对任何”2*,有xz.yz e,从而有XZELO yzeL,即x,y£H「这证明对于任何串乂我们将X在等价关系RM和下的等价类分别记为印M和印L.由于RM7小,我们有=[划「因此,的等价类个数大于等于的等价类个数又由于RM的等价类就是各状态所接受的语言,从而与这些状态是一一对应的,所以RM的等价类个数等于M的状态数这证明引理的第二个结论成立□我们将用RL的等价类作为状态构造一个接受L的最小DFAO
2.米希尔•奈罗德定理定理
2.1Myhill-Nerode正规语言L的最小DFA的状态个数恰好等于RL的等价类个数证明
1.构造最小DFA根据上面的引理,的等价类个数是有限的,我们用这些等价类作为有限自动机的状态构造一个DFA如下其中状态集=£*/,即等价类集合,2是L的符号表,开始状态S=⑻,Qf={[x]\xeL}9即L内的串的等价类都是接受状态,L外的串的等价类都是非接受状态,对于任何状态国和符号々£2,S[x].a=[xa]9即自动机在状态区下扫描字符〃时就进入状态比旬
2.论证ML的正确性我们对输入串的长度用归纳法,将证明对于任何输入串龙£2*,有x eL[x]由于同是也的开始状态,所以2£心[幻假设对于任何长度不超过某个数的串,都有xeL[x]o令为任一输入符号根据假设,也在处理完X后进入状态印根据ML的转移函数,ML在状态印下处理字符后进入状态[M],所以M被状态[刈]所接受这样我们就证明了断言
2.
1.1由此不难推出如下结论对于任何输入串x,都有L[x]=[x]事实上,令y£[x],则因=回,从而y££[对,所以[%]口,[%]下面证明L[x]7[幻令Z G£[%]o我们只需证明Z£[x]根据
2.
1.1,我们有Z£L[Z]因此,Z既被状态区所接受又被状态国所接受由于ML是DFA,接受输入串的状态只能是唯一的,所以印二⑵于是我们有Z£[x]这样我们就证明了乙[幻=[同由此可知,也接受的语言就是乙
3.论证ML的最小性根据上面的引理
1.4,立刻可知ML是最小DFA□推论
2.2如果不考虑状态名称上差异,则每个正规语言的最小DFA是唯一的证明设M是正规语言L的最小DFAO M只要更改各状态的名称就完全变为定理
2.1证明中所构造的ML由于M是L的最小DFA,根据Myhill-Nerode定理,M的状态个数二的等价类个数因此,RM的等价类个数二RL的等价类个数根据上面的引理,RMCL,从而RM=RL.由此可知,对于任何输入串x,M中都有相应地存在唯一状态q恰好接受x的等价类,即Lq=[x]因此,M中各状态与其所接受的等价类之间是一一对应的我们将接受区的状态改名为集合区注意,由于不同状态所接受的等价类是不相交的,所以这个改名是可行的,即不会导致两个不同状态使用同一个名称令a是任何输入符号,则改名后的M在状态区下处理a后进入某个后继状态由于该后继状态接受xa,所以该后继状态所接受的等价类应当是[xa],从而该状态为[xa]由此可以看出,改名后的M完全变成了定理
2.1证明中所构造的私□
3.DFA的最小化方法首先,删除所有的无用状态,即从起始状态出发不能到达的状态这样做并不改变原DFA的识别功能其次,对DFA的状态集合进行分割定义
3.1设M是一个DFAo1M的任何终止状态与非终止状态是可分离的2M的两个状态p与q是可分离的,当且仅当存在串w分别从这两个状态出发可以到达终态与非终态引理
3.2对于状态p和q,若存在字符a,使得状态bp,a与3q,a是可分离的,则p与q是可分离的U评氏可分离~~©引理
3.3对于状态p和q,若存在某个状态既与p不可分离又与q不可分离,则p和q是不可分离的状态分割法第1步,将终止状态与非终止状态相分离,得初步划分Q-Q「,Qf第2步,对当前划分中的每个子集做进一步的划分方法如下以当前所得的划分为标准,应用引理
3.2和
3.3,确定当前子集中的所有可分离的状态对,据此划分该子集重复第2步,直到没有可分离状态对时为止注根据引理
3.2不难看出,状态分割法是正确的,即对于任何DFA,根据该方法所构造的DFA是等价的并且是最小的例
3.4给定NFA图O1用状态子集法得DFA现在我们需要最小化该DFA解该DFA的状态集记为Q={0,1,2,3,4,5}首先将Q划分为拒绝状态集和接受状态集等两个部分口户{{0,1,2},{3,4,5}}其次,对当前划分中的集合继续尝试划分口2={{01},{2},{3,4,5}}口3={{0},{1},{2},{3,4,5}}根据口3,{3,4,5}中不存在可分离的状态对,所以“3就是最后所得的划分最后,画出所得最小DFA如下
4.用Myhill-Nerode定理证明非正规语言定理
4.1Myhill-Nerode语言L是正规的当且仅当的等价类个数是有限的证明若L是正规语言,则根据引理
1.4,及有有限个等价类反之,若有有限个等价类,则根据RL,可以按照Myhill-Nerode定理
2.1证明中的方法构造出接受L的有限自动机区,所以L是正规语言□例
4.1用Myhill-Nerode定理证明L二值叱5工1}不是正规语言关键找出无限个等价类证明设/nW孔注意到aWEL且优任£根据RL的定义可知,an与心不等价因此,侬]和[a叫是两个不相同的等价类从而L有无限多个等价类根据Myhill-Nerode定理,L不是正规语言练习
4.2用Myhill-Nerode定理证明L={卬诚卬£0|1+}不是正规语言
1.正规语言类的封闭性根据本讲义的定义易知,正规语言类在并、连接和星闭包等正规运算下都是封闭的定理若A是正规语言,则A,是正规语言注A的补集是相对于A的字母表上所有串而言的证明设M是接受A的DFA将M的接受状态改为非接受状态,将非接受状态改为接受状态,则所得的DFA接受A的补集事实上,由于M是DFA,所以对于语言A的字母表上任何串来说,M都有某个状态接受该输入串因此,M的所有非接受状态所接受的串构成A的补集证毕思考若M是接受语言A的NFA,则将M的接受状态改为非接受状态,将非接受状态改为接受状态,所得的NFA接受A补吗?定义
1.2(乘积有限自动机)设M,N是两个具有相同输入符号表的DFA,则M和N的乘积有限自动机MN定义如下
(1)若M和N的开始状态为0和0,,则MN的开始状态为(0,0)
(2)若(p,p)是MN的状态,则对于任何输入符号a,(p,p,)的a-转移后继状态为(q,q,)当且仅当p的a・转移后继状态为q且p的a-转移后继状态为
(3)对于MN的任何状态(p,p)该状态是MN的接受状态当且仅当p和p,分别是M和N的接受状态例L3令A为所有被2整除的二进制自然数,B为所有被3整除的二进制自然数再令M,N是分别接受A和B的DFA试构造乘积有限自动机MN定理
1.7若A是正规语言,则AR也是正规语言证明设M是接受A的DFA由M构造接受AR的带空转移的NFA如下
(1)逆转所有转移的方向;
(2)添加一个新的开始状态,空转移到所有的接受状态;
(3)将M的开始状态指定为唯一的接受状,其中状态都是非接受状态不能证明这个NFA恰好接受A RO证毕定理L8若A,B是正规语言,则A/3={z|存在使彳导X=尸}是正规语言。