计算理论习题答案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）=
升级会员 