形式语言与自动机课件ch3.9b-3.10

1CollegeofComputerScience&Technology,BUPT第五讲3.9(part2)右线性语言的封闭性3.10双向和有输出的有限自动机2CollegeofComputerScience&Technology,BUPT右线性语言的封闭性上节从文法产生的角度证明了右线性语言及其并，积，闭包是正则集；本节用有限自动机接受的语言来证明。(书P103~)1.设Ｌ１和Ｌ２是右线性语言，证明Ｌ１∪Ｌ２为右线性语言构造NFAM＝(Q，T，δ，q0，F)Q＝Q1∪Q２∪｛q0｝q0是新的起始状态Ｆ１∪Ｆ２当εＬ１，εＬ２Ｆ１∪Ｆ２∪｛q０｝否则F=M形如:3CollegeofComputerScience&Technology,BUPT右线性语言的封闭性2.设Ｌ１和Ｌ２是右线性语言，证明Ｌ１Ｌ２为右线性语言(书P104~)构造NFAM＝(Q，T，δ，q0，F),其中Q=Q１∪Q２q0=q1Ｆ２当q2F2Ｆ１∪Ｆ２当q2∈F2F=M形如:4CollegeofComputerScience&Technology,BUPT右线性语言的封闭性3.设Ｌ１是右线性语言，证明L１*是右线性语言(书P106~)构造NFAM＝(Q，T，δ，q0，F),Q=Q1∪｛q０｝q０是新的起始状态,F=Ｆ1∪｛q０｝L１*形如5CollegeofComputerScience&Technology,BUPT右线性语言的封闭性4.设Ｌ１是右线性语言，证明L１是右线性语言证明：构造接受Ｌ1的M＝(Q，T，δ，q0，F)其中Q=Q1∪｛γ｝γ是一个新状态TT1q0=q1Ｆ＝(Q1－Ｆ1)∪｛γ｝(即将Ｍ1的终止状态变为M的非终止状态)δ定义为:当a∈T1，则δ(q，a)=δ1(q，a)—保留原有函数当a∈T－T1，则δ(q，a)=γ—遇到原来没有的字符全转至γ.对任意a∈T，δ(γ，a)＝γ6CollegeofComputerScience&Technology,BUPT右线性语言的封闭性例:(书P108)对下图的Ｍ1,求Ｌ(Ｍ1)7CollegeofComputerScience&Technology,BUPT右线性语言的封闭性例:设DFAＭ1＝（｛q０,q４｝,｛ａ,ｂ｝,δ１，q０,｛q３,q４｝）对Ｔ＝｛ａ，ｂ，ｃ｝,求Ｌ(Ｍ1)8CollegeofComputerScience&Technology,BUPT右线性语言的封闭性5.证明Ｌ1∩Ｌ２是封闭的证明：∵Ｌ1∩Ｌ２＝Ｌ1∪Ｌ２∴得证6.证明右线性语言对于置换是封闭的.(略--自学)9CollegeofComputerScience&Technology,BUPT补充：构造自动机的“交”通过构造证明，说明正则语言在交运算下封闭。设两个DFAM1＝(Q1，T，δ1，q1，F1)M2＝(Q2，T，δ2，q2，F2)构造新的DFAM,M＝(Q1xQ2，T，δ，[q1，q2]，F1xF2)对一切p1∈Q1,p2∈Q2，a∈T，δ（[p1，p2],a）=[δ1（p1,a）,δ2（p2,a）]则L（M）=L（M1）∩L（M2）10CollegeofComputerScience&Technology,BUPT有关正则语言的几个判定性质判定正则语言是否为空判定正则语言中是否包含特定的字符串判定两个正则语言是否相等11CollegeofComputerScience&Technology,BUPT判定正则语言是否为空可由如下步骤递归地计算可达状态集合：判定算法测试从初态是否可达某一终态.先求所有可达状态的集合，若其中包含终态，则该正规语言非空，否则为空语言。算法复杂度设有限自动机的状态数目为n，上述判定算法的复杂度为O(n2).基础：初态是可达的：归纳：设状态q是可达的，若对于某个输入符号或，q可转移到p，则p也是可达的：12CollegeofComputerScience&Technology,BUPT判定正则语言中是否包含特定的字符串判定算法从初态开始，处理输入字符串w，如果可以结束于某一终态，则该正规语言中包含w，否则不包含w。算法复杂度设输入字符串w的长度|w|=n，上述判定算法的复杂度为O(n).以DFA表示正则语言以正则表达式表示正则语言将其转化为等价的NFA，然后执行上述过程.以NFA（或NFA）表示正则语言可以将其转化为等价的DFA，然后执行上述过程；也可以直接模拟其处理字符串的过程，判定算法的复杂度为O(n2s),其中n为字符串的长度，s为NFA（或NFA）的状态数目.13CollegeofComputerScience&Technology,BUPT判定两个正则语言是否相等判定算法可由采取如下步骤：算法复杂度以上算法的复杂度即填表算法的复杂度，其上限为O(n4)；可以适当设计填表算法的数据结构，使其复杂度降为O(n2).1.先将两个正则语言的表达形式都转化为DFA，问题转化为两个DFA是否是等价的；2.适当重命名，使两个DFA没有重名的状态；3.将两个DFA相并，构造一个新的DFA，原来的终态仍是终态，转移边不发生任何变化，取任何一个状态为初态；4.对新构造的DFA运用填表算法，如果原来DFA的两个初态不可区别，则这两个正则语言相等，否则不相等.14CollegeofComputerScience&Technology,BUPT双向有限自动机(2DFA)定义:读入一个字符之后，读头既可以左移一格，也可以右移一格，或者不移动的有限自动机，为双向有限自动机.确定的双向有限自动机:每读入一字符，必须向左或右移动，不考虑不移动的情况.15CollegeofComputerScience&Technology,BUPT2DFA的形式定义2DFAM＝(Q，T，δ，q0，F)δ是从Q×T→Q×{L，R}的映射.即δ(q，a)=(p，R)或δ(q，a)=(p，L)（在状态q，读入a，进入状态p，读头向右(向左)移一格）用格局描述:设有ω1qω2ω1---已输入串q---当前状态ω2---待输入串δ(q，am+1)=(p，R)的格局表示:a1a2…amqam+1…an┣a1a2…am+1pam+2…anδ(q，am+1)=(p，L)的格局表示:a1a2…amqam+1…an┣a1a2…am-1pamam+1…an16CollegeofComputerScience&Technology,BUPT2DFA2DFA接受的字符串集合是:L(M)={ω|q０ω┣*ωq，qF}例:书P113例1.其状态图为b,R17CollegeofComputerScience&Technology,BUPT有输出的有限自动机有输出的有限自动机是有限自动机的一个类型.这类自动机在有字符输入时，不仅存在状态转换，同时引起字符输出.根据输入字符，自动机状态，输出字符三者之间关系，可有两类有输出的自动机:米兰机(Mealy):输出字符与输入字符及状态有关.摩尔机(Moore):输出字符仅与状态有关.最大优点:节省状态!18CollegeofComputerScience&Technology,BUPT米兰机米兰机形式定义:M＝(Q，T，R，δ，g，q0)其中Q有限状态集合T有限输入字母表R有限输出字母表δ:Q×T→Q转换函数g:Q×T→R输出函数q0:初始状态q0Qδ和g函数共同描述了米兰机的工作状况.19CollegeofComputerScience&Technology,BUPT米兰机米兰机图形表示:δ(p，a)=qg(p，a)=bPqa/b例:(P115例2)设计米兰机，其输出是输入字符个数的模3数解:输出字母表R={0，1，2}.设输入字母表T={a},M的状态数应有3个，记录已输入字符个数的模3数.Q={q0，q1，q2}分别表示输入字符数模3=0,1,220CollegeofComputerScience&Technology,BUPT米兰机例:（P115例3）设计米兰机，其输入{0，1}*，当输入串有奇数个1时，输出1.当输入串有偶数个1时，输出0.解:需二个状态{q0，q1}q0表示输入串有偶数个1，q1表示输入串有奇数个121CollegeofComputerScience&Technology,BUPT课堂练习设语言L由0，1组成，且字符串的最后两个字符相同.构造米兰机M，输出Y/N表示输入串是否属于L.解:设状态集Q为初始状态q0状态p0表示输入串最后字符为0状态p1表示输入串最后字符为122CollegeofComputerScience&Technology,BUPT课堂练习练习:(书P12219题)设计米兰机，输入是0，1组成的串，要求输出串对输入串延迟两个时间单位.解:M＝(Q，T，R，δ，g，q0)，T={0，1}R={0，1}分析:可能的状态---即一个输入在输出前可能处于的状态Q:00q0001q0110q1011q11Q={q00，q01，q10，q11}23CollegeofComputerScience&Technology,BUPT课堂练习初始情况:刚开始工作时输入前两个字符，输出为ε24CollegeofComputerScience&Technology,BUPT摩尔机摩尔机的输出只与到达的状态有关形式定义:M＝(Q，T，R，δ，g，q0)g:QRδ:QTQ图形表示:δ(q，a)=pg(p)=b2q,b1p,b2a25CollegeofComputerScience&Technology,BUPT摩尔机例:(书P117例4)设计自动机Ｍ，其输入串{0，1}*，输出是(n1-n0)mod4，n0是ω中含0的个数，n1是ω中含1的个数。四个状态q0，q1，q2，q3分别输出0，1，2，3解:需四个状态，取输出字母表R={0，1，2，3}.26CollegeofComputerScience&Technology,BUPT课堂练习设计摩尔机，接受0，1组成的串，串的首符为1，串中出现且只出现一个0。若接受输出Y，否则输出N。解:L的串应为11*01*M＝(Q，T，R，δ，g，q0)T={0，1}，R={Y，N}设计状态Ａ初始状态Ｂ拒绝接受Ｃ可能接受Ｄ接受Q:27CollegeofComputerScience&Technology,BUPT米兰机和摩尔机的变换已知摩尔机可构造等价的米兰机设摩尔机Ｍ＝(Q,T,R,δ,g,q0)米兰机Ｍ’＝(Q,T,R,δ,g’,q0)如果Ｍ中有δ(q，a)=p，g(p)=b则Ｍ’中有g’(q，a)=b=g(δ(q，a))例:摩尔机米兰机28CollegeofComputerScience&Technology,BUPT米兰机和摩尔机的变换由米兰机也可构造等价的摩尔机－－（略）小结双向自动机，米兰机，摩尔机的共同优点是描述问题清晰，且节省状态.例如:对L=(0+1)*(00+11)(前面米兰机的例子)米兰机只需三个状态而用DFA则不会少于5个状态29CollegeofComputerScience&Technology,BUPT作业：Chap3习题1,9，18题