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

自动机习题答案(0)

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

1.给出接受下列在字母表{0,1}上的语言的确定型有限自动机(DFA)图书P36 (1) 所有倒过来解释成二进制整数时是3的倍数的串的集合。

q0——对应倒过来除以3余数为0的x组成的等价类; q1——对应倒过来除以3余数为1的x组成的等价类; q2——对应倒过来除以3余数为2的x组成的等价类; qs——A的开始状态。

(1) qs——在此状态下有δ(qs,0)= q0;δ(qs,1)= q1 。

(2) q0——满足此状态的x有:x=3*n+0,通过q0倒过来可以推导状态。 倒过来计算,当读入0的时候,x=2*(3n+0),所以,?(q0,0)= q0 当读入1的时候,x=2*(3n+0)+1,所以,?(q0,1)= q1 (3) q1——满足此状态的x有:x=3*n+1,通过q1倒过来可以推导状态。 倒过来计算,当读入0的时候,x=2*(3n+1),所以,?(q1,0)= q2 当读入1的时候,x=2*(3n+1)+1,所以,?(q1,1)= q0 (4) q2——满足此状态的x有:x=3*n+2,通过q2倒过来可以推导状态。 倒过来计算,当读入0的时候,x=2*(3n+2),所以,?(q2,0)= q1 当读入1的时候,x=2*(3n+2)+1,所以,?(q2,1)= q2

(2)、0的个数被5整除,1的个数被4整除的二进制整数串的集合。

2.把下列正则表达式转化成带ε转移的NFA,并把该自动机转化成等价的状态最小的DFA。图书P72 (1)(0+1)01 (2)00(0+1)*

带空串的非确定型自动机:

1)

2)

? 0 0 1 ? 0 1 0, 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 ? 确定型自动机:

0

0 1 1

0, 1 0 0

======================================================================

3.证明:(1)语言{0n|n是2的幂}不是正则语言;图书P88 证明:

记此语言为L。反设L是正则的,则泵引理成立。对于泵引理中相应于L的正整数N, 取 w = 0, 其中M=2,则

w=xyz, |xy|<= N, y≠?且xyiz在L中,i=0,1,2,…. 设xz = 0 p, y = 0 q, 则 xyiz = 0 p+iq?L, i= 0,1,2,… 所以 p+iq = 2Ni, i=1,2,…. 于是 (p+(i+1)q)/(p+iq)≥2,

令 i趋于无穷大,则由以上不等式可得 1≥2,矛盾。 (2)语言{anbnci|i≤n}不是上下文无关语言。图书P195 证明:

记此语言为L。反设L是上下文无关的,则泵引理成立。对于泵引理中相应于L的正整数N, 取 z = aNbNcN, 则z?L且|z| ? N,故

z=uvwxy, |vwx|<= N, vx≠?且uviwxiy?L,i=0,1,2,…. 于是可知vwx最少含一个字母、最多含两个字母。

当vx只含一个字母时,若此字母为a或b, 则uv0wx0y中a与b的个数不相同,因此uv0wx0y?L,矛盾;若此字母为c, 则uv2wx2y中c的个数多于b的个数,因此uvwxy?L,矛盾。

当vx恰含两个字母时,若为a,b, 则uv0wx0y中b的个数少于c的个数,因此uv0wx0y?L,矛盾;若此二字母为b,c, 则uv0wx0y中a与b的个数不相等,因此uv0wx0y?L,矛盾。

所以, L 不是上下文无关的。

============================================================= 4.设计下推自动机以及上下文无关文法来识别或生成下列语言:{anbm|n≤m}。 图书P174

确定型下推自动机:

考虑语言L$={anbm$ | n?m},即原来L中每个串加上$作为结束标志的语言。以接受状态方式接受L$的DPDA为:

P= ( Q,Σ, ?,? ,q0 ,Z0,F), 其中 Q={ q0 , q1 , q2 }, Σ={a,b,$}, ?= {a,b, Z0}, F= {q2}, 转移函数? 的定义为:

2

2

MN

? (q0,a, Z0)={(q0, aZ0)}, ? (q0,a,a)={(q0, aa)}, // 第一阶段 ? (q0,b, Z0)={(q1, Z0)}, ? (q0,b,a)={(q1, ?)},

? (q1,b,a)={(q1, ?)}, ? (q1,b, Z0)={(q1, Z0)}, // 第二阶段

? (q1, $, Z0) = {(q2, ?)}, ? (q0, $, Z0)={(q2, ?)}, // 转入终结状态

上下文无关文法:

a,Z0/a Z0 a,a/aa b,Z0/ Z0 b,a/?

b,Z0/ Z0 b,a/? $,Z0/ ? $,Z0/ ?

构造一个上下文无关文法G,生成语言

L={ anbm: n?m }。 可以用以下文法产生语言L:

G: S S1 因此构成文法G=(V,T,P,S) S1 a S1b|? 其中:V={S,S1} S1 S1b T={a,b}

P={S S1, S1 a S1b| S1b| b|? }

5.分别设计图灵机M,M接受语言P229 (1){0n1n2n|n≥1}。

思路:最初带上为 0 0…0 1 1…1 2 2…2 B B B ……

可以通过判断0、1、2的个数是否相同:消除一个0、然后消除一个1、最后消除一个2。消除的0用X代替、消除的1用Y代替、消除的2用Z代替。图灵机启动后,经过一段运行,输入带上的符号串一般情况为 X…X0…0 Y…Y1…1Z…Z2…2BB 重复循环。

可能出现的边界情况为:

X…XX…X Y…YY…YZ…Z2…2BB X…XX…XY…Y1…1Z…Z2…2BB X…X0…0 Y…YY…YZ…Z2…2BB

X…X0…0 Y…Y1…1Z…ZZ…ZBB X…X0…0 Y…YY…YZ…ZZ…ZBB

Y / YZ / ZY / YZ / ZX / Xq5B / Bq6Startq00 / Xq11 / Yq22 / Zq3Y / Y0 / 0Z / Z1 / 1Z / Z1 / 1Y / Y0 / 0q4(2){ω|ω∈{0,1}*,ω含有相同个数的0和1}。 (注意与P224例8.2中0n1n的区别) 下面是转移函数表

state 0 1 B - - - X Y (q0,Y,R) (q1,Y,R) (q2,Y,R) - q0 (q2,X,R) (q1,X,R) (qf,B,R) - q1 (q3,Y,L) (q1,1,R) - q2 (q2,0,R) (q3,Y,L) - q3 (q3,0,L) (q3,1,L) - qf - - - (q0,X,R) (q3,Y ,L) 思路是TM(图灵机)沿着带子不断地向后和向前游历.符号X 和 Y用来替代已经

相互抵消了的0和1.差别在于,X保证其左侧没有不能匹配的0和1,因此带头从不移到X的左侧。但是 Y的左侧可能有0和1。对照转移表,下面说明每个转移的含义.

(状态转移表的q0行) 起初在状态q0,TM读到一个0或1,将其记在状态里(q1=读到一个1;q2=读到一个0),并将所读到的用一个X抵消(也就是用X替换0或1).有一个例外,如果TM在状态q0看到空格,则所有0和1已匹配,因此进入状态qf输入被接受.

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

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