资源描述：
《形式语言自动机――有限自动机与右线性文法(四)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五讲3.9(part2)右线性语言的封闭性3.10双向和有输出的有限自动机1CollegeofComputerScience&Technology,BUPT右线性语言的封闭性上节从文法产生的角度证明了右线性语言及其并，积，闭包是正则集；本节用有限自动机接受的语言来证明。(书P103~)设Ｌ１和Ｌ２是右线性语言，证明Ｌ１∪Ｌ２为右线性语言构造NFAM＝(Q，T，δ，q0，F)Q＝Q1∪Q２∪｛q0｝q0是新的起始状态Ｆ１∪Ｆ２当εＬ１，εＬ２Ｆ１∪Ｆ２∪｛q０｝否则F=M形如:2CollegeofComputerScience&Technology,BUPT
2、右线性语言的封闭性设Ｌ１和Ｌ２是右线性语言，证明Ｌ１Ｌ２为右线性语言(书P104~)构造NFAM＝(Q，T，δ，q0，F),其中Q=Q１∪Q２q0=q1Ｆ２当q2F2Ｆ１∪Ｆ２当q2∈F2F=M形如:3CollegeofComputerScience&Technology,BUPT右线性语言的封闭性设Ｌ１是右线性语言，证明L１*是右线性语言(书P106~)构造NFAM＝(Q，T，δ，q0，F),Q=Q1∪｛q０｝q０是新的起始状态,F=Ｆ1∪｛q０｝L１*形如4CollegeofComputerScience&Technology,BUPT右线性语言的封闭性设
3、Ｌ１是右线性语言，证明L１是右线性语言证明：构造接受Ｌ1的M＝(Q，T，δ，q0，F)其中Q=Q1∪｛γ｝γ是一个新状态TT1q0=q1Ｆ＝(Q1－Ｆ1)∪｛γ｝(即将Ｍ1的终止状态变为M的非终止状态)δ定义为:当a∈T1，则δ(q，a)=δ1(q，a)—保留原有函数当a∈T－T1，则δ(q，a)=γ—遇到原来没有的字符全转至γ.对任意a∈T，δ(γ，a)＝γ5CollegeofComputerScience&Technology,BUPT右线性语言的封闭性例:(书P108)对下图的Ｍ1,求Ｌ(Ｍ1)6CollegeofComputerScience&Tech
4、nology,BUPT右线性语言的封闭性例:设DFAＭ1＝（｛q０,q４｝,｛ａ,ｂ｝,δ１，q０,｛q３,q４｝）对Ｔ＝｛ａ，ｂ，ｃ｝,求Ｌ(Ｍ1)7CollegeofComputerScience&Technology,BUPT右线性语言的封闭性证明Ｌ1∩Ｌ２是封闭的证明：∵Ｌ1∩Ｌ２＝Ｌ1∪Ｌ２∴得证6.证明右线性语言对于置换是封闭的.(略--自学)8CollegeofComputerScience&Technology,BUPT有关正则语言的几个判定性质判定正则语言是否为空判定正则语言中是否包含特定的字符串判定两个正则语言是否相等9CollegeofCo
5、mputerScience&Technology,BUPT判定正则语言是否为空可由如下步骤递归地计算可达状态集合：判定算法测试从初态是否可达某一终态.先求所有可达状态的集合，若其中包含终态，则该正规语言非空，否则为空语言。算法复杂度设有限自动机的状态数目为n，上述判定算法的复杂度为O(n2).基础：初态是可达的：归纳：设状态q是可达的，若对于某个输入符号或，q可转移到p，则p也是可达的：10CollegeofComputerScience&Technology,BUPT判定正则语言中是否包含特定的字符串判定算法从初态开始，处理输入字符串w，如果可以结束于某一终
6、态，则该正规语言中包含w，否则不包含w。算法复杂度设输入字符串w的长度
7、w
8、=n，上述判定算法的复杂度为O(n).以DFA表示正规语言以正规表达式表示正规语言将其转化为等价的NFA，然后执行上述过程.以NFA（或NFA）表示正规语言可以将其转化为等价的DFA，然后执行上述过程；也可以直接模拟其处理字符串的过程，判定算法的复杂度为O(ns2),其中n为字符串的长度，s为NFA（或NFA）的状态数目.11CollegeofComputerScience&Technology,BUPT判定两个正则语言是否相等判定算法可由采取如下步骤：算法复杂度以上算法的复
9、杂度即填表算法的复杂度，其上限为O(n4)；可以适当设计填表算法的数据结构，使其复杂度降为O(n2).1.先将两个正规语言的表达形式都转化为DFA，问题转化为两个DFA是否是等价的；2.适当重命名，使两个DFA没有重名的状态；3.将两个DFA相并，构造一个新的DFA，原来的终态仍是终态，转移边不发生任何变化，取任何一个状态为初态；4.对新构造的DFA运用填表算法，如果原来DFA的两个初态不可区别，则这两个正规语言相等，否则不相等.12CollegeofComputerScience&Technology,BUPT双向有限自动机(2DFA)定义:读入一个字符之后，
10、读头既可以左移一格，也可
