计算理论习题答案CHAP1new.docx
- 文档编号:15317444
- 上传时间:2023-07-03
- 格式:DOCX
- 页数:89
- 大小:413.99KB
计算理论习题答案CHAP1new.docx
《计算理论习题答案CHAP1new.docx》由会员分享,可在线阅读,更多相关《计算理论习题答案CHAP1new.docx(89页珍藏版)》请在冰点文库上搜索。
计算理论习题答案CHAP1new
第一章
1.1图给出两台DFAMM和M2的状态图.回答下述有关问题•
a.M的起始状态是qi
b.M的接受状态集是{q2}
c.M2的起始状态是qi
d.M的接受状态集是{qi,q4)
e.对输入aabb,Mi经过的状态序列是qi,q2,q3,qi,qi
f.M接受字符串aabb吗?
否
g.M接受字符串&吗?
是
i.2给出练习2.i中画出的机器M和M的形式描述.
M=(Qi,工,Si,qi,Fi)其中
1)Q={qi,q2,q3,};
2)工={a,b};
3)Si为:
a
b
qi
q2
q
i
q2
q3
q
3
q3
q2
q
i
4)
qi是起始状态
5)
Fi={q2}
M=(Q,艺,S
2,q2,F
2)
其中
i)
Q={qi,q2,q3,q4}
J
2)
工={a,b};
3)
S2为:
a
b
qi
qi
q
2
q2
q3
q
4
q3
q2
q
i
q4
q3
q
4
3)q2是起始状态
1.3
4)F2={q1,q4}
DFAM的形式描述为({q1,q2,q3,
q4,q5},{u,d},S,q3,{q3}),其中S在表2-3中给
d
d
d
试画出此机器的状态图。
出。
d
u
d
q1
q2
q3
q4
画出识别下述语言的
DFA的状态图
1.6
o
0
0
0,1
0
0
0
0,1
1
1
1
0,1
1
0
0
1
0,1
1
0
0,1
0
0,1
a){w|w从1开始以
b){w|w至少有3个1}
c){w|w含有子串0101}
0结束}
d){w|w的长度不小于3,且第三个符号为0}
3
e){w|w
从0开始且为奇长度,或从1开始且为偶长度}
0
0,1
1
0
1
1
0
0,1
的长度不超过5}
g){w|w
1
1
1v
0,1
0
i){w|w的奇位置均为1}
1
0'
0,1
..「0,1
j){w|w至少含有2个0,且至多含有1个1}
9
0
0
1
0,1
0
1
0
k){「0}
0,1
I){w|w含有偶数个0,或恰好两个1}
m)空集n)除空串外的所有字符串
dx^0,1-^^J*^0,1
1.7给出识别下述语言的NFA且要求符合规定的状态数。
a.{w|w以00结束},三个状态
0,1
b.语言{w|w含有子串0101,即对某个x和y,w=x0101y,5个状态.
c.语言{w|w含有偶数个0或恰好两个1},6个状态。
d.
e.语言0*1*0*0,3个状态。
0
f.语言{£},1个状态
g.语言0*,1个状态。
一>/0
1.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA
证明:
设NFAM={Q工,S,qo,F},F={ri1,”,m}.添加一个状态p后,r-n,”,5分别向p引&箭头,将r-1,”,r-k变为非接受状态,p变为接受状态。
又因为添加&箭头不影响NFA识别语言,所以命题成立。
1.14a证明:
设M是一台语言B的DFA交换M的接状态与非接受状态得到一台新的DFA则这台新的DFA是识别B的补集,因此,正则语言类受在补运算下封闭。
b举例说明:
设M是一台识别语言B的NFA交换M的接受状态与非接受状态得到一台新的NFA这台新的NFA不一定识别B的补集。
NFA识别的语言类在补集下封闭吗?
解释你的回答。
解:
a.M是DFA,M是{Q,刀,S,q°,F},令N={Q,刀,S,qo,Q-F},设co=w炖2,con是字母表上任意字符串,因为M与N均为DFA所以必然存在Q中状态序列r°,r1,,,rn,使得:
r0=q0,S(ri,oi+1)=ri+1,i=0,,,n-1
1)若rn・F贝oB;
2)若r^F,则"Q-F,即N接受o,若o-B,
所以N接受B的补集,即B的补集正则。
所以,正则语言类在补运算下封闭。
b.设B为{0}。
NFAM
可识别它。
._一
依题对它作变换,得到N:
—:
-:
则N识别的语言{£}不是B的子集。
所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。
但是由于NFA识别的语言类与DFA识别的语言类相同,即正则语言类。
由a的证明,正则语言类在补运算封闭,可知,NFA识别的语言类---正则语言类在补运算下封闭。
若NFA识别语言A,必有等价的DFAK别A,从而由a知,可交换DFA的接受与非接受状态构造识别A的补集的DFA,则必有等价的NFA识别A的补集。
只是,该NFA未必有原NFA交换接受与非接受状态构造而成。
1.15给出一个反例,说明下述构造不能证明定理2.24,即正则语言类在星号运算下封闭
设N=(Q,工,Si,qi,Fi)识别A。
如下构造N=(Q,工,Si,qi,Fi)。
N应该识别Ai*。
a.N的状态集是N的状态集
b.
N的起始状态是N的起始状态相同。
c.
d.
F={qi}UFi。
F的接受状态是原来的接受状态加上它的起始状态。
定义S如下:
对每一个q属于Q和每一个a属于工。
召(q,a),若q老R或a式名
®(q,a)o{qi},若F且a^s
6(q,a)=」
解:
设
有一个
i}。
N:
N识别语言A={至少含有一个i},其中输入字母表为{0,i},可知A={空串或至少含
按上述规定构造N的状态图如上。
可以看出L(N)={0,i}*不等于A*.所以如此构造的N不一定识别A*.
i.i6使用定理2.i9中给出的构造,把下图中的两台非确定型有穷自动机转换成等价的确定
型有穷自动机。
a),b)
b
解:
a),b)
i.i9对下述每一个语言,给出4个字符串,2个是这个语言的成员,2个不是这个语言的成
员。
这里假设字母表
艺={a,b}.
**
a.ab
成员:
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.ababab
成员:
aba,bab
非成员:
a,b
g.(_a)b
成员:
b,ab
非成员:
a,bb
h.(a一ba一bb)艺*
成员:
a,bb
非成员:
;,b
1.21使用引理2.32中叙述的过程,把图2-38中的有穷自动机转换成正则表达式
a),
b
1
2
b
a
2
a
解:
a)a*b(a_.ba*b)*
b);_.(ab)a*b[(aaabb)a*b]*(a_.;).
(注:
答案不唯一)
1.29利用泵引理证明下述语言不是正则的。
nnn
a.A1={012|n_0}。
证明:
假设A是正则的。
设p是泵引理给出的关于A1的泵长度。
ppp
令S=012,
•••S是A1的一个成员且S的长度大于P,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。
根据条件3,y中只含0,xyyz中,0比1、2多,xyyz不是A的成员。
违反泵引理的条件1,矛盾。
•••A不是正则的。
*
b.A2={www|w{a,b}}.
证明:
假设A是正则的。
设p是泵引理给出的关于A的泵长度。
ppp
令S=ababab,
•••S是A的一个成员且S的长度大于p,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。
根据条件3,y中只含a,所以xyyz中第一个a的个数将比后两个a的个数多,故xyyz不是A的成员。
违反泵引理的条件1,矛盾。
•A不是正则的。
2门屮n
c.A3={a|n一0}.(在这里,a表示一串2个a.)
证明:
假设A是正则的。
设p是泵引理给出的关于Ab的泵长度
令S=a2"
•••S是A的一个成员且S的长度大于P,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。
即对任意的i_0,xy'z都应在A中,且xy'z与xy'++z的长度都应
...n
是2的幕.而且xyz的长度应是xy'z的长度的2倍(n_1)。
于是可以选择足够大的',
n'.I''.In+1
使得|xy'z|=2>p.但是|xy'z|-|xy'z|=|y|
•••A不是正则的。
1.30下面“证明”0*1*不是正则语言,指出这个“证明”中的错误。
(因为0*1*是正则的,所
以一定错误。
)采用反证法证明。
假设0*1*是正则的。
令P是泵引定理给出的关于0*1*的泵长度。
取S为字符串0P1P。
S是0*1*的一个成员,但是例2.38已证明S不能被抽取。
于是得到矛盾,所以0*1*不是正则的。
nnpp
解:
在例2.38中的语言是{01|n一0},取S为字符串01,S确实不能被抽取;但针
**对语言01,S是能被抽取的。
将S分成三段S=xyz,由泵引理的条件3,y仅包含0,
而xy'z属于语言0*1*,即S能被抽取,故题设中的“证明”不正确。
1.24有穷状态转换器(FST)是确定性有穷自动机的一种类型。
它的输出是一个字符串,而不
仅仅是接受或拒绝。
图
2—39是两台有穷状态状态转换器
0/01/1
2
T1和T2的状态图
T1T
FST的每一个转移用两个符号标记,一个指明该转移的输入符号,另一个指明输出符号。
两个符号之间用斜杠“/”把它们分开。
在T1中,从q1到q2的转移有输入符号2和输出符号1。
某些转移可能有多对输入-输出,比如T1中从5到它自身的转移。
FST在对输入串w计算时,从起始状态开始,一个接一个地取输入符号W…w,并且比照输入标记和符号序列W…w=w
进行转移。
每一次沿一个转移走一步,输出对应的输出符号。
例如,对输入2212011,机器
T1依次进入状态q1,q2,q2,q2,q2,q1,q1,q1和输出1111000。
对输入abbb,T2输出1001。
给出在下述每一小题中机器进入的状态序列和产生的输出。
a.T1对输入串011,输出:
000,状态序列:
q1,q1,q1,q1.
b.Ti对输入串211,输出:
111,状态序列:
qi,q2,q2,q2.
c.T1对输入串0202,输出:
0101,状态序列:
5,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对输入串;,输出:
;,状态序列:
q1。
1.25给出有穷状态转换器的形式定义。
解:
有穷状态转换器FST是一个五元组(Q,工,r,S,qO)
1)Q是一-个由穷集合,叫做状态集
2)工是一个由穷集合,叫做输入字母表
3)r是一个由穷集合,叫做输出字母表
4)S:
QX艺QXr是转移函数
5)q°是起始状态
FST计算的形式定义:
M=(Q2,r,S,q°)是一台由穷状态转换器,w=w^..w是输入字母表上的一个字符串。
若存在Q中的状态序列:
ro,r1,...rn和输出字母表上的一个字符串s=S1,sn,满足下述条件:
1)r0=q。
;
2)S(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},S,q1,{0,1})
其中转移函数为:
0
1
2
q1
q/0
q』0
q2/1
q2
q/0
q2/1
q2/1
有穷状态转换器T2的形式描述为:
T2=({{q1,q2,q3},{a,b},S,q1,{0,1})
其中转移函数为:
a
b
q1
qJ1
qa/1
q2
qa/1
q1/0
q3
q/0
q2/1
1.27给出一台具有下述行为的FST的状态图。
它的输入、输出字母表都是{0,1}。
它输出的
字符串与输入的字符串偶数为相同、奇数位相反。
例如,对于输入
0000111,
它应该输出
1010010。
解:
pqP「一'
s=010,q>0。
由泵引理
1.46证明:
a)假设{010|m,n>0}是正则的,p是由泵引理给出的泵长度。
取
条件3知,|xy|
所以该语言不是正则的。
假设{0n1n|n>0}的补集是正则的,则根据正则语言在补运算下封闭可得{0n1n|n>0}是正则的,这与已知矛盾,故假设不成立。
所以该语言不是正则的。
记c={0m1n|mMn},门c为c的补集,门cP0*1*={0n1n|n>0},已知{0n1n|n>0}不是正则的。
若门c是正则的,由于0*1*是正则的,那么门cP0*1*也应为正则的。
这与已知矛盾,所以门c不是正则的。
由正则语言在补运算下的封闭性可知c也不是正则的。
b){w|w{0,1}*不是一个回文}的补集是{w|w{0,1}*是一个回文},设其是正则的,令p
pqp
是由泵引理给出的泵长度。
取字符串s=010,显然s是一个回文且长度大于p。
由泵引
理条件3知|xy|
而xyyz不再是一个回文,这与泵引理矛盾。
所以{w|w{0,1}*是一个回文}不是正则的。
由正则语言在补运算下的封闭性可知{w|
w{0,1}*不是一个回文}也不是正则的。
1.31对于任意的字符串w=ww2,ww的反转是按相反的顺序排列w得到的字符串,记作w\即w=wn,ww。
对于任意的语言A,记AR={wR|A}证明:
如果A是正则的,则AR也是正则的。
证明:
因为A是正则语言,所以可以用NFA来表示该语言,现在来构造AR的NFA将NFAA中的接受态变为中间态,起始态变为接受态,再添加一新的起始态,并用£箭头连接
至原来的接受态,其它所有的箭头反向。
经过变换后得到NFA变成描述AR的NFA.
「0:
「0‘
工3=彳
0
0,
1
…,1
卜
-0」
L1、
•0/
•V
1.32令
v'3包括所有高度为3的0和1的列向量。
'3上的字符串给出三行0和1的字符串。
把每一行
看作一个二进制数,令B={w最下面一行等于上面两行的和}
例如,
「0、
T
‘0?
11、
0
0
1
wB,
0
0
更B
11J
L0J
1。
:
11」
11:
证明B是正则的
证明:
由题设B的定义可知,
w上面两行之和减去下面一行结果为零,由此可设计
NFAM(Q,
S,q0,F)
0,q1状态表示上
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
q。
{q0}
0
0
{q0}
0
{q0}
{q1}
0
q1
0
{q0}
{q1}
0
{q1}
0
0
{q1}
,其中'=-3oQ={qo,q1}。
qo状态表示上一次运算的进位为
一次运算的进位为1oS由下表给出:
F={q。
}
状态图为:
0
10J
10
1
r0、
1
L0、
仁
1
1、
所以可知自动机M识别的是语言
BR,因此才是正则的。
由题
2-24的结论可知B也是正则的
1.33令
12=
r0、
「1、
•1、
J
.0、
‘0、
.0」
1
1、
0和1的字符串。
把每一行看作
匸包含所有高度为2的0和1的列。
32上的字符串给出两行一个二进制数,令C={wx2*|w下面一行等于上面一行的3倍}
证明C是正则的。
可以假设已知问题2.24中的结果。
证明:
如下的NFA识别C:
其中q°状态表示上一次运算的进位为0,
如下的NFA识别
C:
其中状态
次运算的进位为2。
q°,qi,q2分别表示目前读到的下面的数减上面
1
1.
的情况。
的数的3倍余0,1,2
0
、1J'10J'
12包含所有高度为2的0和1的列
1.34令
j0
12上的字符串给出两行0和1的字符串。
把每一行看作
一个二进制数,令
D={wx2|w上一行大于下一行}
证明D是正则的。
证明:
由题设可设计自动机M=(Q,工,S,q,F),其中Q={qi,q2},F={q2},
转移函数与状态图为:
0
0
0
1
1
0
1
1
q1
{q1}
0
{q2}
{q1}
q2
{q2}
{q2}
{q2}
{q2}
0
[1
[11
1001
1
10J,
10J11JI0.
1J
1.35设刀2与问题2.26中的相同。
把每一行看作0和1的字符串,令E={w';|w的下一行是上一行的反转},证明E不是正则的。
1
「0.
选择字符串s=
、0.
4
证明:
假设E是正则的
P是有泵引理给出的泵长度。
于是s能够被划分为xyz且满足泵引理的条件。
1
根据条件3,y仅能取包含门的部分,当添加一个y时,xyyz不属于E.所以E不是正则
L0」
1.36令B={ak|k是n的整数倍}。
证明对于每一个n_1,Bn是正则的
证明:
设字母表刀为{a},则an是一正则表达式。
所以,(an)*也是正则表达式。
由题意B=(a)*,即B可以用正则表达式表示。
所以,Bn也是正则的。
1.37令cn={x|x是一个二进制数,且是n的整数倍}。
证明对于每一个n1,Cn是正则的。
证明:
下面的DFA识别G:
(正向读)
M=(Q,{0,1},、.,qo,F),其中Q={0,1,2,,,n-1},
、(i,1)=2i+1modn,、(i,0)=(2imodn),i=0,1,2,,,n-1,
起始状态为0,F={0}.
这里i表示当前数modn余i.
下面的DFA识别Gr:
(反向读)
M=(Q,{0,1},:
.,q0,F),其中Q={(i,j)|i,j=0,1,2,,,n-1},
((i,j),1)=(2imodn,(2i+j)modn),、((i,j),0)=(2imodn,j),i,j=0,1,2,,,n-1
起始状态为(1,0),F={(i,0)|i=0,1,,,n-1}.
这里(i,j)表示当前数modn余j,而下一位所表示单位数modn余i(例如,若读下一位将达到k位,则下一位所表示单位数为10k-1).
1.38考虑一种叫做全路径NFA的新型有穷自动机。
一台全路径NFAM是5元组(Q,:
:
.,q°,F).如果M对x'的每一个可能的计算都结束在F中的状态,贝UM接受X。
注意,相反的,普通的NFA只需有一个计算结束在接受状态,就接受这个字符串。
证明:
全路径NFA识
别正则语言。
证明:
一个DFA-定是一个全路径NFA所以下面只需证明,任意全路径NFA都有一个与之等价的DFA
设有一全路径NFAN=(Q,工,S,q0,F),构造一个新与N等价的全路径NFA
Ni=(Q1,
工,S1,q0,
F),
其中Q=Q-{s},s
世Q对于任意Q,ae工
|s(q,a),
q
=s,且S(q,a)
=_;
&1(q,a)=
1{s},q
=s,且S(q,a)
=.一;
{s},
q=s.
现在来构造一个与全路径NFAN等价的DFAM=(Q2,工,S2,q1,F2).其中
1)Q2=Power(Q),即Q的所有子集组成的集合(也即Q的幕集);
2)定义函数E:
Q2Q为:
对任意RQ,E(R)二:
.1(r,;);
r甲
3)qi=E(q。
);
4)对于任意的R属于Q,a属于工,、:
2(R,a)=E“(r,a).
2丿
5)F2={RQ|R二F}。
综上所述,DFA等价于全路径NFA
1.40如果存在字符串z使得xz=y,则称字符串x是字符串y的前缀。
如果x是y的前缀且x工y,则称x是y的真前缀。
下面每小题定义一个语言A上的运算。
证明:
正则语言类在每个运算下封闭。
a)NOPREFIX(A)={宀€A|3的任意真前缀都不是A的元素}
b)NOEXTEND(A)={3€A|3不是A中任何字符串的真前缀}
证明:
假设DFAM=(Q,2,S,q°,F)识别语言A。
a)构造NFAN=(Q,2,S1,q°,F)识别语言NOPREFIX(A。
其中,
7$(q,a)},q^Q—F,a^E
对任意q^F,a=2名®(q,a)=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 理论 习题 答案 CHAP1new