77范文网 - 专业文章范例文档资料分享平台

自动机习题答案(0)(2)

来源:网络收集 时间:2019-04-14 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

(状态转移表的q0行和q1行)在状态q1,TM向右移,寻找一个0.如果找到了,用Y 代替0,TM进入状态q3向左移寻找一个X.类似地,状态q2寻找一个1来匹配0.

(状态转移表的q3行)在状态q3, TM向左移直至找到最右边的X.此时,又一次进入状态q0,向右移穿过Y直至找到0,1,或空格,循环又一次开始. 6.设A=(Q,Σ,δ,q0,F)为DFA,证明:PPT正则语言的性质

(1)L=L(A)非空的充分必要条件是存在x∈Σ*,使得且δ*(q0,x)∈F,|x|<|Q|

(2)L=L(A)为无穷集的充分必要条件是,存在x∈Σ*,使得|Q|≤|x|<2|Q|且δ*(q0,x) ∈F,其中|Q|表示状态集Q的元素个数,|x|表示串x的长度。

============================================================= 7.讨论并论证上下文无关语言关于交运算的封闭性,以及上下文无关语言与正则语言的交运算的性质(PPT第8章54页)。 定理 8-2 CFL 在交运算下不封闭的。

设 L1={ 0n1n2m | n, m≥1 },L2={ 0n1m2m | n, m≥1 }。

G1:S1?AB 显然,L(G1)=L1、L(G2)=L2 。

A?0A1|01 L= L1∩L2 = { 0n1n2n | n≥1} 不是 CFL。 B?2B|2 所以,CFL 在交运算下是不封闭的。

G2:S?AB

A?0A|0 B?1B2|12

8.设L是字母表Σ上的正则语言,a∈Σ,证明:商Σ/a={ω∈Σ*|ωa∈L}也是正则语言。

证明:若L是任一正则语言,设接受L的DFA 为A= (Q,Σ,δ,q0, F) ,据此可以构造另一台DFA B=(Q,Σ,δ,q0, F1),其中前四项与A相同,而取 F1={q| ??(q,a)?F},

则B是接受的正则语言,即商Σ/a={ω∈Σ*|ωa∈L}是正则语言。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库自动机习题答案(0)(2)在线全文阅读。

自动机习题答案(0)(2).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/zonghe/591322.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: