正则语言非正则运算的封闭性--《佳木斯大学学报(自然科学版)》2005年02期
正则语言非正则运算的封闭性
【摘要】：　本文用构造的方法严格证明了识别正则语言三种非正则运算的确定型有穷自动机的存在性,进而得出正则语言类在非正则运算"∩"、"-"以及" "下的封闭性的结论,并具体给出识别三类语言运算的确定型有穷自动机模型.
【作者单位】：
【关键词】：
【基金】：
【分类号】：O158【正文快照】：
自1956年形式语言问世以及乔姆斯基(NoamChomsky)于1959年给出了形式文法的4种类型(无限止型、上下文有关、上下文无关以及正则文法)以来,形式语言和有穷自动机理论有了快速的发展.随着计算机及其高级语言的广泛应用,形式语言与计算机编译理论的联系愈加紧密.由于作为形式文
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【共引文献】
中国期刊全文数据库
李正朝;[J];解放军外国语学院学报;1999年06期
彭家法;[J];安徽大学学报(哲学社会科学版);2004年04期
程家兴,陈万里,宋杰;[J];安徽大学学报(自然科学版);2004年04期
谢克藻;[J];安康师专学报;2000年04期
李宝健;[J];北方工业大学学报;2002年03期
车燕,任开隆;[J];北京联合大学学报;2001年02期
王郁昕;[J];北京联合大学学报;2005年02期
孙凤芝,程霜梅,刘建群;[J];长春师范学院学报;2004年10期
黄强;李敏;楼新远;;[J];成都信息工程学院学报;2006年02期
张健;[J];重庆师范大学学报(自然科学版);2005年01期
中国重要会议论文全文数据库
于伟昌;;[A];中国辞书学会双语词典专业委员会第四届年会暨学术研讨会论文集[C];2001年
张绍飞;;[A];数学·物理·力学·高新技术研究进展（一九九六·第六期）——中国数学力学物理学高新技术交叉研究会第6届学术研讨会论文集[C];1996年
王廷明;吴伟民;;[A];第一届中国智能计算大会论文集[C];2007年
中国博士学位论文全文数据库
陈泽华;[D];太原理工大学;2007年
奚悦;[D];大连理工大学;2007年
张玉芳;[D];重庆大学;2001年
蔡波;[D];西北工业大学;2002年
王可;[D];天津大学;2003年
杜世宏;[D];中国科学院研究生院（遥感应用研究所）;2004年
吴金华;[D];武汉大学;2003年
宋永圭;[D];复旦大学;2004年
张劲松;[D];华中科技大学;2004年
侯霞;[D];中国科学院研究生院（软件研究所）;2005年
中国硕士学位论文全文数据库
王福贵;[D];山西大学;2007年
石磊;[D];大连理工大学;2008年
耿霞;[D];山东科技大学;2007年
刘秀莲;[D];太原理工大学;2007年
詹海波;[D];华中科技大学;2006年
杨凯;[D];华南师范大学;2007年
袁冬莉;[D];重庆大学;2007年
朱彦;[D];广西师范大学;2000年
化建宁;[D];河北农业大学;2001年
武优西;[D];河北工业大学;2002年
【相似文献】
中国期刊全文数据库
郭聿琦;[J];兰州大学学报(自然科学版);1980年02期
,李廉;[J];兰州大学学报(自然科学版);1981年04期
,郭聿琦;[J];兰州大学学报(自然科学版);1982年03期
唐常杰,张一立;[J];科学通报;1982年23期
,李廉;[J];兰州大学学报(自然科学版);1983年02期
郭聿琦,王水汀,李廉;[J];数学学报;1983年03期
莫绍揆;;[J];南京大学学报(自然科学版);1983年04期
郭聿琦;[J];科学通报;1984年22期
黄育潜;;[J];江西师范大学学报(自然科学版);1985年01期
郭聿琦;[J];数学杂志;1986年04期
中国硕士学位论文全文数据库
柏明强;[D];四川师范大学;2001年
王贱珍;[D];青岛大学;2003年
王静;[D];郑州大学;2005年
严奇琦;[D];上海交通大学;2007年
张忠;[D];浙江大学;2007年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备74号正则语言在连结、星号运算下封闭的DFA证明
NFA）理论。M.Sipser在《Introduction to the Theory of Computation》中用确定型有穷自动机（简记作DFA）理论给出了正则语言类在并运算下的封闭性，但没有用确定型有穷自动机理论给出正则语言类在连结和星号运算下的封闭性。本文试图尝试完成这一工作。1 如果一个语言被一台有穷自动机，则称它是正则语言。2 设A和B是两个语言，正则运算连结和星号是指：:A·B ＝{xy:x∈A∧y∈B}:A*＝{x1x2…xi…xk:k≥0且每一个xi∈A}3 确定型有穷自动机是一个5元组（Q，Σ，δ，q0，F），其中1）Q是一个有穷集合，叫做状态集。2）Σ是一个有穷集合，叫做字母表。3）δ：Q×Σ→Q是转移函数。4）q0∈Q是起始状态。 5）F Q是状态集。1 正则语言类在连结运算下封闭。DFA M1A1，DFA M2识别A2，M.Sipser认为：“设计的（确定型）有穷自动机M不是当M1或M2时接受，而应该是当它的输入可以被分成两段，M1接受第一段M2接受第二段时，M才接受。问题是M不知道在什么地方把它的输入分开（即，在什么地方第一段结束和第二段开始）。”因此，M.Sipser放弃了用确定型有穷自动机理论来证明正则语言类在连结运算下的封闭性；而引入了非确定性的新技术，用非确定型有穷自动机理论来完成其证明。M，同时模拟M1和M2。当输入符号w1w2…wn一个接一个地来到时，我们首先M1和M2的起始状态q1和p1。对于输入w1，因为它既可能属于A1又可能属于A2。如果它属于A1，假定δ1（q1， w1）＝q2，那么M1和M2分别处于q2和p1状态；如果它属于A2，假定δ2（p1， w1）＝p2，那么M1和M2分别处于q1和p2状态。这时，我们需要的状态是q2p1和q1p2。与此类似，对于输入w2，当处于状态q2p1时，可能进入q3p1和q2p2状态；当处于状态q1p2时，可能进入q2p2和q1p3状态。这时，我们需要记住的状态是q3p1、q2p2和q1p3。……所以，我们需要记住的所有状态是M1的状态集和M2的状态集的迪卡儿积的所有非空子集。当输入结束，如果我们所记住的状态中存在qipj，其中qi属于M1的接受状态并且pj属于M2的接受状态，则接受这一字符串；否则，拒绝。证明：设DFA M1识别A1，DFA M2识别A2，其中M1＝（Q1，Σ，δ1，q1，F1）， M2＝（Q2，Σ，δ2，p1，F2）A1·A2的DFA M，这里M ＝（Q，Σ，δ，q，F）。1） Q ＝ {x:x∈P（y）-{φ}， y ＝{r1r2:r1∈Q1∧r2∈Q2}} 2） 字母表Σ与M1、M2的相同。3） 转移函数δ定义如下：对于每一个状态x∈Q和每一个a∈Σ，令δ（x，a）＝{qipj+1:qipj∈x，pj+1＝δ2（pj，a）}∪{qi+1pj:qipj∈x，qi+1＝δ1（qi，a）} 4）q＝{q1p1}5）F＝{x:x∈P（y）∧ z（z∈x∧z＝qipj∧qi∈F1∧pj∈F2，y＝{qipj: qi∈Q1∧pj∈Q2}}由M的构造，不难验证：对任一字符串w1w2…wn，如果w1w2…wn∈A1·A2，当且仅当M接受w1w2…wn。2 正则语言类在星号运算下封闭。 DFA M1识别A，我们要设计一台识别A*的DFA M。设想自己就是这样的一台确定型有穷自动机M。当输入符号w1w2…wn一个接一个地来到时，我们首先记住M的起始状态q1。对于输入w1，假定δ1（q1， w1）＝q2，则进入q2；……，对于输入wi，δ1（qi， wi）＝qi+1，如果qi是M1一接受状态，则我们除了须记住状态qi+1外，还必须记住分叉δ1（q1， wi），因为w1w2…wi-1可能是语言A中的字符串，也可能是语言A中的字符串的前一部分。因此，此时我们要记住的状态是M1中的状态qi+1和δ1（q1， wi）。如此进行下去，每遇到M1一接受状态，都发生分叉。这样，我们实际需记住的全部状态为所有M1状态的非空子集。当输入结束，如果所记住的M1的状态子集中存在一M1一接受状态，则接受；否则，拒绝。M中增加接受状态q0。增加接受状态q0是为了保证DFA M接受空串 。为什么没有将M1的状态的子集{q1}直接设计为接受状态，这是因为将{q1}设计为M的接受状态并作为M的起始状态固然可以使M接受空串 ，但是也可能加进其他不想要的字符串。当存在某一qi，如果δ1（qi，a）＝q1就会出现这种情况。增加接受状态q0，并且令转移函数为δ（q0，a） ＝{δ1（q1，a）}（使q0发挥了的q1计算功能），这保证了在M的状态图中q0只有射出的箭头，而没有射入的箭头，从而排除了q0接受除空串 外的其他字符串的可能性。 证明：设DFA M1识别A，其中M1＝（Q1，Σ，δ1，q1，F1）A*的DFA M，这里M ＝（Q，Σ，δ，q，F）。1） Q ＝（P（Q1）-{φ}）∪{q0} 2） 字母表Σ与M1的相同。3） 转移函数δ定义如下：对于每一个状态Qi∈（P（Q1）-{φ}）∪{q0}和每一个a∈Σ，令δ（q0，a） ＝{δ1（q1，a）}δ（Qi，a）＝{qi+1:qi+1＝δ1（qi，a），qi∈Qi} 若﹁ x（x∈Qi∧x∈F1）；或＝{qi+1:qi+1＝δ1（qi，a），qi∈Qi}∪{δ1（q1，a）} 若﹁ x（x∈Qi∧x∈F1）. 4）q＝q05）F＝{Qj: Qj∈P（Q1）∧ x（x∈Qj∧x∈F1}∪{q0}.由M的构造，不难验证：对任一字符串w1w2…wn，如果w1w2…wn∈A*，当且仅当M接受w1w2…wn。 Q简化。实际设计时，在状态图中将无箭头射入的状态删去，这不会影响计算功能。[1] 张立昂等译 [美]Michael Sipser着 《计算理论导引》 机械工业出版社2000年版。[2] 刘田等译 [美]Harry R.Lewis， Christos H.Papadimitriou着 《计算理论基础》 清华大学出版社2000年版。[3] [美]Harry R.Lewis， Christos H.Papadimitriou着 《Elements of the Theory of Computation》 清华大学出版社1999年版。[4] 许明贤等译 [英]罗杰·彭罗斯着 《皇帝新脑》 湖南科学技术出版社1996年版。（原载《自动化理论、技术与应用》第8卷，解放军出版社2001年6月）
查看: 420|
佛缘网站的运行需要大量的资金及人力，以下法宝流通的收益将用于佛缘网站的建设。感恩您的支持！
非经营性互联网文化单位备案：
地址：福建省厦门市湖里区金湖一里6号409室　邮编：361010　联系人：陈晓毅
电话：（值班时间：9：00-17：30）　QQ群：8899063　QQ： 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
计算理论课后题及答案2
下载积分：1000
内容提示：计算理论课后题及答案2
文档格式：DOC|
浏览次数：16|
上传日期： 19:51:01|
文档星级：
该用户还上传了这些文档
计算理论课后题及答案2
官方公共微信计算理论习题解答_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
计算理论习题解答
上传于||文档简介
&&唐​常​杰​的​计​算​理​论​习​题​解​答
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩41页未读，继续阅读
你可能喜欢 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
计算理论导引习题答案[第2版]CHAP2new
下载积分：30
内容提示：计算理论导引习题答案[第2版]CHAP2new
文档格式：PDF|
浏览次数：174|
上传日期： 15:30:57|
文档星级：
该用户还上传了这些文档
计算理论导引习题答案[第2版]CHAP2new
官方公共微信