计算理论习题解答Word格式.doc
- 文档编号:733660
- 上传时间:2023-04-29
- 格式:DOC
- 页数:44
- 大小:664KB
计算理论习题解答Word格式.doc
《计算理论习题解答Word格式.doc》由会员分享,可在线阅读,更多相关《计算理论习题解答Word格式.doc(44页珍藏版)》请在冰点文库上搜索。
d
1.6画出识别下述语言的DFA的状态图。
a){w|w从1开始以0结束}
1
0,1
b){w|w至少有3个1}
c){w|w含有子串0101}
d){w|w的长度不小于3,且第三个符号为0}
e){w|w从0开始且为奇长度,或从1开始且为偶长度}
或
f){w|w不含子串110}
g){w|w的长度不超过5}
h){w|w是除11和111以外的任何字符}
i){w|w的奇位置均为1}
j){w|w至少含有2个0,且至多含有1个1}
k){ε,0}
l){w|w含有偶数个0,或恰好两个1}
m)空集n)除空串外的所有字符串
1.7给出识别下述语言的NFA,且要求符合规定的状态数。
a.{w|w以00结束},三个状态
b.语言{w|w含有子串0101,即对某个x和y,w=x0101y},5个状态.
e
c.语言{w|w含有偶数个0或恰好两个1},6个状态。
d.语言{0},2个状态。
e.语言0*1*0*0,3个状态。
f.语言{ε},1个状态。
g.语言0*,1个状态。
2.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。
证明:
设NFAM={Q,Σ,δ,q0,F},F={ri1,……,rik}.添加一个状态p后,ri1,……,rik分别向p引ε箭头,将ri1,……,rik变为非接受状态,p变为接受状态。
又因为添加ε箭头不影响NFA识别语言,所以命题成立。
2.14a证明:
设M是一台语言B的DFA,交换M的接状态与非接受状态得到一台新的DFA,则这台新的DFA是识别B的补集,因此,正则语言类受在补运算下封闭。
b举例说明:
设M是一台识别语言B的NFA,交换M的接受状态与非接受状态得到一台新的NFA,这台新的NFA不一定识别B的补集。
NFA识别的语言类在补集下封闭吗?
解释你的回答。
解:
a.M是DFA,M是{Q,∑,δ,q0,F},令N={Q,∑,δ,q0,Q-F},设ω=ω1ω2…ωn是字母表上任意字符串,因为M与N均为DFA,所以必然存在Q中状态序列r0,r1,…,rn,使得:
r0=q0,δ(ri,ωi+1)=ri+1,i=0,…,n-1
1)若rnÎ
F则ωÎ
B;
2)若rnÏ
F,则rnÎ
Q-F,即N接受ω,若ωÏ
B,
所以N接受B的补集,即B的补集正则。
所以,正则语言类在补运算下封闭。
b.设B为{0}。
NFAM:
可识别它。
依题对它作变换,得到N:
则N识别的语言{ε}不是B的子集。
所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。
但是由于NFA识别的语言类与DFA识别的语言类相同,即正则语言类。
由a的证明,正则语言类在补运算封闭,可知,NFA识别的语言类---正则语言类在补运算下封闭。
若NFA识别语言A,必有等价的DFA识别A,从而由a知,可交换DFA的接受与非接受状态构造识别A的补集的DFA,则必有等价的NFA识别A的补集。
只是,该NFA未必有原NFA交换接受与非接受状态构造而成。
1.15给出一个反例,说明下述构造不能证明定理2.24,即正则语言类在星号运算下封闭。
设N=(Q1,Σ,δ1,q1,F1)识别A1。
如下构造N=(Q1,Σ,δ1,q1,F1)。
N应该识别A1*。
a.N的状态集是N1的状态集。
b.N的起始状态是N1的起始状态相同。
c.F={q1}∪F1。
F的接受状态是原来的接受状态加上它的起始状态。
d.定义δ如下:
对每一个q属于Q和每一个a属于Σ。
设N1识别语言A={至少含有一个1},其中输入字母表为{0,1},可知A*={空串或至少含有一个1}。
a,b
a
b
2
N1:
N:
按上述规定构造N的状态图如上。
可以看出L(N)={0,1}*不等于A*.所以如此构造的N不一定识别A*.
3
1.16使用定理2.19中给出的构造,把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。
a),b),
a),b)
23
123
Æ
12
2.13给出生成练习2.4中语言的正则表达式。
(注:
答案不唯一)
a.{w|w从1开始以0结束}1Σ*0.
b.{w|w至少有3个1}Σ*1Σ*1Σ*1Σ*.
c.{w|w含有子串0101}Σ*0101Σ*.
d.{w|w的长度不小于3,且第三个符号为0}ΣΣ0Σ*.
e.{w|w从0开始且为奇长度,或从1开始且为偶长度}0(ΣΣ)*È
1Σ(ΣΣ)*.
f.{w|w不含子串110}(0È
10)*1*.
g.{w|w的长度不超过5}eÈ
ΣÈ
ΣΣÈ
ΣΣΣÈ
ΣΣΣΣÈ
ΣΣΣΣΣ.
h.{w|w是除11和111以外的任何字符}0Σ*È
10Σ*È
110Σ*È
111ΣΣ*.
i.{w|w的奇位置均为1}(1Σ)*(eÈ
1).
j.{w|w至少含有2个0,且至多含有1个1}0*(00È
010È
001È
100)0*.
k.{ε,0}.εÈ
0.
l.{w|w含有偶数个0,或恰好两个1}(1*01*0)*1*È
0*10*10*.
m.空集.Æ
.
n.除空串外的所有字符串ΣΣ*.
1.19对下述每一个语言,给出4个字符串,2个是这个语言的成员,2个不是这个语言的成员。
这里假设字母表Σ={a,b}.
a.a*b*成员:
ab,aab非成员:
aba,ba
b.a(ba)*成员:
ab,abab非成员:
abb,aa
c.a*È
b*成员:
aaa,bbb非成员:
ab,ba
d.(aaa)*成员:
aaa,aaaaaa非成员:
a,aa
e.Σ*aΣ*bΣ*aΣ*成员:
aba,aaba非成员:
aa,abb
f.abaÈ
bab成员:
aba,bab非成员:
a,b
g.(eÈ
a)b成员:
b,ab非成员:
a,bb
h.(aÈ
baÈ
bb)Σ*成员:
a,bb非成员:
e,b
1.21使用引理2.32中叙述的过程,把图2-38中的有穷自动机转换成正则表达式。
a),b),
解:
a)a*b(aÈ
ba*b)*
b)eÈ
(aÈ
b)a*b[(aaÈ
abÈ
b)a*b]*(aÈ
e).
(注:
答案不唯一)
1.29利用泵引理证明下述语言不是正则的。
a.A1={0n1n2n|n³
0}。
证明:
假设A1是正则的。
设p是泵引理给出的关于A1的泵长度。
令S=0p1p2p,
∵S是A1的一个成员且S的长度大于p,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。
根据条件3,y中只含0,xyyz中,0比1、2多,xyyz不是A1的成员。
违反泵引理的条件1,矛盾。
∴A1不是正则的。
b.A2={www|wÎ
{a,b}*}.
假设A2是正则的。
设p是泵引理给出的关于A2的泵长度。
令S=apbapbapb,
∵S是A2的一个成员且S的长度大于p,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。
根据条件3,y中只含a,所以xyyz中第一个a的个数将比后两个a的个数多,故xyyz不是A2的成员。
∴A2不是正则的。
c.A3={a2n|n³
0}.(在这里,a2n表示一串2n个a.)
假设A3是正则的。
设p是泵引理给出的关于A3的泵长度。
令S=a2p,
即对任意的i³
0,xyiz都应在A3中,且xyiz与xyi+1z的长度都应是2的幂.而且xyi+1z的长度应是xyiz的长度的2n倍(n³
1)。
于是可以选择足够大的i,使得|xyiz|=2n>
p.但是|xyi+1z|-|xyiz|=|y|£
p.即|xyi+1z|<
2n+1,矛盾。
∴A3不是正则的。
1.30下面“证明”0*1*不是正则语言,指出这个“证明”中的错误。
(因为0*1*是正则的,所以一定错误。
)采用反证法证明。
假设0*1*是正则的。
令P是泵引定理给出的关于0*1*的泵长度。
取S为字符串0p1p。
S是0*1*的一个成员,但是例2.38已证明S不能被抽取。
于是得到矛盾,所以0*1*不是正则的。
在例2.38中的语言是{0n1n|n³
0},取S为字符串0p1p,S确实不能被抽取;
但针对语言0*1*,S是能被抽取的。
将S分成三段S=xyz,由泵引理的条件3,y仅包含0,而xyiz属于语言0*1*,即S能被抽取,故题设中的“证明”不正确。
b/1
a/0
b/0
a/1
1.24有穷状态转换器(FST)是确定性有穷自动机的一种类型。
它的输出是一个字符串,而不仅仅是接受或拒绝。
图2—39是两台有穷状态状态转换器T1和T2的状态图。
2/1
0/0
1/0
1/1
T1T2
FST的每一个转移用两个符号标记,一个指明该转移的输入符号,另一个指明输出符号。
两个符号之间用斜杠“/”把它们分开。
在T1中,从q1到q2的转移有输入符号2和输出符号1。
某些转移可能有多对输入-输出,比如T1中从q1到它自身的转移。
FST在对输入串w计算时,从起始状态开始,一个接一个地取输入符号w1¼
wn,并且比照输入标记和符号序列w1¼
wn=w进行转移。
每一次沿一个转移走一步,输出对应的输出符号。
例如,对输入2212011,机器T1依次进入状态q1,q2,q2,q2,q2,q1,q1,q1和输出1111000。
对输入abbb,T2输出1001。
给出在下述每一小题中机器进入的状态序列和产生的输出。
a.T1对输入串011,输出:
000,状态序列:
q1,q1,q1,q1.
b.T1对输入串211,输出:
111,状态序列:
q1,q2,q2,q2.
c.T1对输入串0202,输出:
0101,状态序列:
q1,q1,q2,q1,q2。
d.T2对输入串b,输出:
1,状态序列:
q1,q3.
e.T2对输入串bbab,输出:
1111,状态序列:
q1,q3,q2,q3,q2.
f.T2对输入串bbbbbb,输出:
110110,状态序列:
q1,q3,q2,q1,q3,q2,q1。
g.T2对输入串e,输出:
e,状态序列:
q1。
1.25给出有穷状态转换器的形式定义。
有穷状态转换器FST是一个五元组(Q,Σ,Г,δ,q0)
1)Q是一个由穷集合,叫做状态集
2)Σ是一个由穷集合,叫做输入字母表
3)Г是一个由穷集合,叫做输出字母表
4)δ:
Q×
Σà
Г是转移函数
5)q0是起始状态
FST计算的形式定义:
M=(Q,Σ,Г,δ,q0)是一台由穷状态转换器,w=w1w2¼
wn是输入字母表上的一个字符串。
若存在Q中的状态序列:
r0,r1,¼
rn和输出字母表上的一个字符串s=s1…sn,满足下述条件:
1)r0=q0;
2)δ(ri,wi+1)=(ri+1,si+1),i=0,1,¼
n-1
则M在W的输入下输出s.
1.26利用你给练习2.20的答案,给出练习2.19中画出的机器T1和T2的形式描述。
有穷状态转换器T1的形式描述为:
T1=({q1,q2},{0,1,2},δ,q1,{0,1})
其中转移函数为:
q1/0
q2/1
有穷状态转换器T2的形式描述为:
T2=({{q1,q2,q3},{a,b},δ,q1,{0,1})
q3/1
1.27给出一台具有下述行为的FST的状态图。
它的输入、输出字母表都是{0,1}。
它输出的字符串与输入的字符串偶数为相同、奇数位相反。
例如,对于输入0000111,它应该输出1010010。
0/1
1.46证明:
a)假设{0n1m0n|m,n≥0}是正则的,p是由泵引理给出的泵长度。
取s=0p1q0p,q>
0。
由泵引理条件3知,|xy|≤p,故y一定由0组成,从而字符串xyyz中1前后0的数目不同,即xyyz不属于该语言,这与泵引理矛盾。
所以该语言不是正则的。
b)假设{0n1n|n≥0}的补集是正则的,则根据正则语言在补运算下封闭可得{0n1n|n≥0}是正则的,这与已知矛盾,故假设不成立。
记c={0m1n|m≠n},┐c为c的补集,┐c∩0*1*={0n1n|n≥0},已知{0n1n|n≥0}不是正则的。
若┐c是正则的,由于0*1*是正则的,那么┐c∩0*1*也应为正则的。
这与已知矛盾,所以┐c不是正则的。
由正则语言在补运算下的封闭性可知c也不是正则的。
c){w|wÎ
{0,1}*不是一个回文}的补集是{w|wÎ
{0,1}*是一个回文},设其是正则的,令p是由泵引理给出的泵长度。
取字符串s=0p1q0p,显然s是一个回文且长度大于p。
由泵引理条件3知|xy|≤p,故y只能由0组成。
而xyyz不再是一个回文,这与泵引理矛盾。
所以{w|wÎ
{0,1}*是一个回文}不是正则的。
由正则语言在补运算下的封闭性可知{w|wÎ
{0,1}*不是一个回文}也不是正则的。
1.31对于任意的字符串w=w1w2…wn,w的反转是按相反的顺序排列w得到的字符串,记作wR,即wR=wn…w2w1。
对于任意的语言A,记AR={wR|Î
A}证明:
如果A是正则的,则AR也是正则的。
因为A是正则语言,所以可以用NFA来表示该语言,现在来构造AR的NFA,将NFAA中的接受态变为中间态,起始态变为接受态,再添加一新的起始态,并用ε箭头连接至原来的接受态,其它所有的箭头反向。
经过变换后得到NFA变成描述AR的NFA.
…
S3=
1.32令
å
3包括所有高度为3的0和1的列向量。
3上的字符串给出三行0和1的字符串。
把每一行看作一个二进制数,令
B={wÎ
3*|w最下面一行等于上面两行的和}
例如,
而
Î
B
Ï
证明B是正则的。
由题设B的定义可知,w上面两行之和减去下面一行结果为零,由此可设计NFAM(Q,Σ,δ,q0,F),其中å
=å
3。
Q={q0,q1}。
q0状态表示上一次运算的进位为0,q1状态表示上一次运算的进位为1。
δ由下表给出:
q0
{q0}
{q1}
F={q0}
状态图为:
所以可知自动机M识别的是语言BR,因此BR是正则的。
由题2-24的结论可知B也是正则的。
S2=
1.33令
S2包含所有高度为2的0和1的列。
S2上的字符串给出两行0和1的字符串。
C={wÎ
2*|w下面一行等于上面一行的3倍}。
证明C是正则的。
可以假设已知问题2.24中的结果。
如下的NFA识别CR:
其中q0状态表示上一次运算的进位为0,
q1状态表示上一次运算的进位为1,q2状态表示上一次运算的进位为2。
如下的NFA识别C:
其中状态q0,q1,q2分别表示目前读到的下面的数减上面
的数的3倍余0,1,2的情况。
1.34令
D={wÎ
2*|w上一行大于下一行}。
证明D是正则的。
由题设可设计自动机M=(Q,Σ,δ,q,F),其中Q={q1,q2},F={q2},
转移函数与状态图为:
{q2}
1.35设∑2与问题2.26中的相同。
把每一行看作0和1的字符串,令E={wÎ
2*|w的下一行是上一行的反转},证明E不是正则的。
p
假设E是正则的,令p是有泵引理给出的泵长度。
选择字符串s=。
于是s能够被划分为xyz且满足泵引理的条件。
根据条件3,y仅能取包含的部分,当添加一个y时,xyyz不属于E.所以E不是正则的.
1.36令Bn={ak|k是n的整数倍}。
证明对于每一个n³
1,Bn是正则的。
设字母表∑为{a},则an是一正则表达式。
所以,(an)*也是正则表达式。
由题意Bn=(an)*,即Bn可以用正则表达式表示。
所以,Bn也是正则的。
1.37令Cn={x|x是一个二进制数,且是n的整数倍}。
1,Cn是正则的。
下面的DFA识别Cn:
(正向读)
M=(Q,{0,1},d,q0,F),其中Q={0,1,2,…,n-1},
d(i,1)=2i+1modn,d(i,0)=(2imodn),i=0,1,2,…,n-1,
起始状态为0,F={0}.
这里i表示当前数modn余i.
下面的DFA识别CnR:
(反向读)
M=(Q,{0,1},d,q0,F),其中Q={(i,j)|i,j=0,1,2,…,n-1},
d((i,j),1)=(2imodn,(2i+j)modn)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 理论 习题 解答
![提示](https://static.bingdoc.com/images/bang_tan.gif)