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

2019-04-14 14:21

(状态转移表的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}是正则语言。


自动机习题答案(0)(2).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:用电分类常识

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: