离散数学基础-习题参考答案-第19章 图灵机

第19章图灵机

笫19章习题

19.1(1)输入110110：

^1101105FIgilOllOB他(qo,])=(dI,A))

.llgoOHOB伍(")=(如JR))

HllOqollOB3(qo,O)=(qo,0.A))

HHOlgjlOB(6(<7O,L)=

.HOUgoOB=(“J,A))

FllOUO9oB(6(qo,Oj=(《),(),△))

停机状态go€尸，接受(1101102=54IO,54+3=18整除).

(2)输入101010：

的101010〃1-l^iOWlOB(8(qo，L)=(qd))

H10Q2101075(6(qi,0)=((72：。,R))

I-10100106(6(3,1)=(®1,A))

HIOIOQI10B(“<72,0)=(qi,0,A))

f-10101(/oOB(“Qi,"=(qoJ,R))

i-101010^)5(6(qo,0j=(“),0,/?))

停机状态如€F,接受(1010102=4210,42+3=14整除).

(3)输入111111：

9O11111WH19111111B(3(如,1)=(“1,1,A))

=(goJH))

I-Uq0UUB

i-(AQO，L)=(qi,L7?))

HUUqollB=(wd))

f-(“Qo,"=(qiJ,R))

i-IIIIH90B=(qo,l,A))

停机状态qo€尸,接受(nini2=6310,63+3=21整除).

(4)输入100000：

4)1000003i-Iqi00000。(<5((/0,1)=(s/,W)

f-10g20000B0j=A))

HlOOqiOOOO(J(92,0)-(91.0./?))

1-1000g200B(“41,0)=("2。"))

f-1000017iOB(“<72,0)=(<7i。H))

1-1000003月3(<7I,0)=(<72,0.A))

停机状态(12fF,拒绝(IOOOOO2=32io,32+3=10余2).

19.2(1)输入aaa：

Bq()aaaB1-BaqnaaB(3(qo，a)=(%,a,H))

nBa(iqaaB0((7a,Q)=(q°,a,R))

1-BaaaqaB(6(qa,a)=(qa,a,H))

1-Baaqn\{al3=(*"))

第19章习题

nBuqL(iBB(6(如A3Q)=(<7L,B,L))

I-Bq^aaBIS做在⑷=（我此为）

1-q^BaaBB他(",。)=(qL,a,L))

HBqEaaBB(6(qL,B)=(qE-))

i-BBq()(iBB0SE,Q)=(qoH))

i-I3I3aqaBB(6(qo,a)=Sa、a,R))

i-BBqa\[aBB(6(qa,B)=(qaM,B,L))

i-(a(GaA八a)=(7L,B,L))

(d((/L，B)=(QE-))

停机状态拒绝.

⑵输入aba：

Bq()abaBiBaqnbaB(b(qo.Q)=(qa,a,R))

FB(il)qa(iB(6(qa,£)=(%,b,H))

HI3abaq(lB(“q”Q)=(%,&H))

nBabqaMaB(3(%,6)=(qaM,B,L))

FI3aqLbBB(8(征”1)=(%,8,L))

HBqiabBB(6(qL,b)=(qL,b,L))

t-q^BabBB(8(qL>a]=(qL,a,L))

HBqt-abBB(6(%B)=SE,BH))

nBBq()bBB(6(3。)=(qo,B,R))

FBBbqbBB(6(qo,b)=(qb,，R))

FBRqbAibBB—)

nBqiBBBB(6(qb」w")=(<7L,B,L))

F1313(^131313(“〃，〃)=(%,5A))

停机状态在：（广，拒绝.

（3）输入bb：

BqobbBFI3bqi,bI38(qo、b)=(m，AA))

J-Bbbqi,B0(如，b)=(仇，6A))

•-BbqbMbB(6(qb,13)=(qbM,13,L))

f-BqJ)I3B=(〃"))

i-q^BUBB（6（在加=的也为）

HI3(lF：bBB(6(qL,8)=(qE,B,K))

f-BBqoBB(63M=(qo,B,H))

停机状态如€尸,接受.

(4)输.入baba：

I3qobabaBf-I3bqi,(ibaB(3(qo,b)=(qb,b,R))

i-Bbaq^baB0(物⑷=(%,a,A))

h-Bbabqt,aB(6(qbM=

nBbabaq^B伍（的,。）=（佻,。,n））

1Bbabqi^fdU(6(如,〃)=(qbA/,〃,L))

停机状态qbMiF,拒绝.

nnn

19.3图灵机M4识别语言L4={abc17/20）.

设状态集合Q={40,仇国2,93,%,北},其中:

第19章习题

。W：初始状态（准备替换最左侧Q或检查结束）

。3：已替换。为以向右寻找占

。伙：已替换力为V，向右寻找，

。（?3：已替换C为Z,向左返回起点

。检查阶段（验证剩余符号均为y.z）

o45：终结状态（接受状态）

纸带字母表r={a,AC,0n,y,z},终结状态集F={痣}.

转移函数方的定义如下：

—我,g)=(%产㈤（替换Q为i,右移寻找b）

3(—)=(的,仍H)（无Q可替换，进入检查阶段）

b(qo,_B)=(q5H)（空串接受）

“qi,Q)=Gi,a,R)（跳过未处理的。）

-qiM=(gi,y,R)（跳过已匹配的b标记）

”qi，b)=(Q2,0,N)（替换6为九右移寻找C）

“，2,匕）=3，b,R）（跳过未处理的6）

”02,z)=(72,2.R)（跳过已匹配的C标记）

6(t72,c)=(Q3,Z'H)（替换c为z,右移准备返回）

*<73,。)=(，3,a⑷（左移跳过。）

%3,6)=(如也L)（左移跳过b）

6(43,c)=3,c,L)（左移跳过c）

3(034)=(Q3ML)（左移跳过已匹配的，））

浏3,2)=(如,z,L)（左移跳过已匹配的c）

”93,6)=3,8/)（在最右端左移）

6(—)=(qo,£,R)（遇到起点标记z,右移开始下--轮）

6(Q4,g)=(■!/,■)（跳过沙）

河如⑶=（四,名"）（跳过Z）

3(%,B)=a,B,R)（纸带扫描完毕,接受）

19.4(1)输入abc:

qoabcF3HxqibcB伍(go,。)=(仇,二H))

Hxyq2cBS(qiM=(MOD)

H^yzq-iB(6((/2,c)=(93,Z,H))

ixyq^zBWq3,B)=(q3,B,L))

•-xq-iyzB3(Q3,z)=(q3fz,L))

做如。=（（的期㈤）

f-xqQiizB=So,④,A))

Hxyq.\zB(6(qoM=(q,i,少衣))

Fxyzq4B0s4,zj=(74,2.7?))

nxyzBq^B(6(q4,B)=(q5,B,R))

停机状态的€乱接受.

(2)输入aabc:

q()aabcBnxq\abcB(8(qo,a)=(qi,2,A))

FT(iq\lx：13(“(71,a)=(gi,a：A))

Hxayq2cB(“Qi,—=-2,协H))

Hxayzq^B口（。2⑼=（钙,名A））

3

第19章习题

Fxayq2zB(6(q3,B)=(q3,B,L))

F工aq3nzl3—3,2)=(Q3,Z,L))

Hxq^ayzB

nq^xayzB伍（如。）=（的必乃）

Fxq^ayzB做―)=

ixxqiyzB(8(qo，a)=Si,①，A))

nxxyq\zB(6(/,£|=®,0,K))

停机状态qi£F,拒绝.

输入aubbccc.

q()aabbcccBH工q、abbcccB(3(qo,a)=A))

nxaqibbcccB(“矶,Q)=(Q1M⑹)

Hxayq-ibcccB(“41,3=-2,。,—))

HxaybqicccB(*<72,与=(0,AA))

i-xaybzq^ccB(“G2,C)=(<73,2,H))

Hxaybq^zccB(6(43,c)=(q：3，C,£))

Hxayq^bzccB(6-3,z)=(Q3,Z,E))

i-xaq^ybzccB83,b)=(q3,b,L))

f-xq^aybzccB(3(43,y)=(每夕⑷)

Hq^XGybzccB(狗3,Q)=((13,a,L))

Hxq()aybzccB-3㈤=(go,c,H))

H2:2^iybzccB(3(qo,a)=A))

n笈①yqibzccB("qiM=(qi,y,H))

Hxxyyq-2ZccB(6(qi，3=3,5R))

HxxyyzqoccB伍(02,2)=(Q2,Z,H))

Hxxyyzzq^cB(“G2,C)=(93,2,7?))

Hxxyyzq-^zcB(6(43,0)=(q：3，c，L))

Hxxyyq^zzcB(d(Q3,z)=(<73,Z,L))

1xxyq-syzzcB(“Q3,Z)=(q3,z,£))

nxxq-iytjzzcl3做©U)=(43,2//))

Hxq^xyyzzcB(33，")=(43，!//))

nxxq^yyzzcB他(如心)=(qo,①，A))

nxxyq^yzzcB9(qoM=(。4,。㈤)

Hxxyyq^zzcB3(q4M=(%6R))

Hxxyyzq4zcB(3(%,z)=(%,%/?))

Hxxyyzzq4cB伍((/4,zj=(6/4,Z./?))

停机状态%4E拒绝.

输入ace:

qoaccBHxqiccB(6((jo,aj=(qi,1,H))

停机状态qd乩拒绝.

输入abb:

qoabbI31tqibbB(3(如㈤=(仇山,H))

Hcyq2bB(6(伙,一=(42,"A))

Hxybq-2^(%2,与=(42。〃))

停机状态（72<R拒绝.

第19章习题

19.5(1)输入QioQn(表示二进制数11和01)

(6(，O,QIO)=SO，QIO，H))

1BBaioanqoB3(qo,Qii)=(qo,Qii,A))

n1313(i\[)n\(i\]13(aqo,B)=(q],6Z))

(6(6,。11)=(。2,。,功)

F(6(q2,Qio)=(Q2,0,E))

Bq2B00B

n(7361008(3(%0=丽1⑷)

i-Bqf100B伍(如])=(盯出H))

停机状态qj©W,输出为100(二进制).

(2)输入劭1。10(表示二进制数01和10)

BBqoQoiQioBi66aoiqoQi()6(B(qo,a(n)=(<Zo,«oi,/?))

i-1313a()]ayoq()13(3(。0,。10)=(go,®。，A))

aBBaoiliaioB0(%,B)=(gi,BZ))

nBBqiamlB(<iio)=(gi,LE))

1bqiimu0(qi,Qoi)=(qi,l,L))

FBBq/11B(6(内⑻=(",6H))

停机状态qfc尸,输出为11(二进制).

(3)输入的—式表示二进制数100和101)

BBqoanaooaoiBi36ali(/。。。。。。*(6(QO,Q11)=(go,Qii,R))

I-〃&2114)0如.01"(3(qo,aoo)=(4o,Qoo,A))

I-7?/?«!i^OO^OlQO^(3(qo,Q(n)=So,a(H,A))

i-BBanfloo</i«oiB

(6(q0,B)=(gi,B,L))

(3(qi,Qoi)=(gi」,L))

f-BBqianQIB("qi,Qoo)=(仇,。,功)

F因280013(6(qi,aii)=(q2,0,£))

n(73^1001B(33)=丽1,乃)

H

/?gz1001B(如31)=(0,况码)

停机状态qf£P,输出为1001(二进制).

(4)输入—(表示二进制数10和10)

RBqoQ.iiQooBi-BBawq^a^B3(qo,Qii)=(9o,au,/?))

i-13I3ai]a^()q()I3(5(go，aoo)=(4。,。00,A))

iI3J3ai\qiUQoB0(qo,B)=(qi,B,E))

i-iOZ?@(qi,Qoo)=(qi，0,£))

n13q2B0QI3("qi,Qii)=(42,。/))

i-q3B100I3(3(仅，0=(31/))

FBQ/IOOB(6(-%AA))

停机状态(lfe。输出为100(二进制).

19.6(1)输入1+1

Bq°l+IBBl(j()+113("qoJj=MbA))

H(a(qo,+)=SoJR))

BllqolB

(6(qo,l)=(go,1,R))

(b(go,〃)=(gi"))

(狗I,D=(02,B,E))

nBqAiBBW?2,l)=(Q2,1,E))

第19章习题

Fq2B\.\BB(8(。2,1)=(0，1，上))

13gf111313传«%6)=(0，氏A))

停机状态qf€R输出为11（一进制）.

⑵输入111+11

Bgolll+11BHBlgoll+1113f-Bllgol+11BH5111go+11B(三次8(qo，L)=SoJ,A))

HBini^oii^(6(qo，+j=(如,i,R))

HBlllllqolSHBlUlllqoB(两次6(^4)=(如,1,A))

KBlllllgilB(<5(7O,B)=(71,B,L))

I-BllllqzlBB(6(qi,1)=(q2，B,L))

Fmilq2U1313HBllq2111gBHBl^UUBBHB^lllUBB

(四次42,1)=(0,"))

Hq2BWWXBB(B(q2,D=(q2,1,£))

FBqflllllBB(6(92,B)=(qj,B,R))

停机状态（1/€。输出为进制).

⑶输入1+11

JJq°l+114HBlq()+11B(d(q。,1)=(绯1,A))

iBllqoll月(8(qo,+)=(%,1,H))

H5111如151BllllqoB(两次“q0,1)=(q0,1,/?))

HBHIQUB(3(go,8)=(gi,〃,L))

1BllqzlBB(6(gi,1)=(仇,仇心))

HBlq-AIBBHBq-ilUBB(两次6(q2,1)=(0,1,L))

nq2BlllI3B(3((/2,D=(<72,1,£))

f-Bq/lllBB(d(q2,B)=(qf,B,R))

停机状态qSEF,输出为111(一进制).

⑷输入U+1

BqdIB一Blqol+1B»-311go+IB(两次3(的，1)=(的，1,A))

卜BlllqolB9(go,+)=

FB1U17OB(“qoJ)=So,l,H))

iBlllqilB(<5(qo，B)=

HBU(721BB(3(0,1)=((72,6,L))

iBlqzllBBHZ?!/2111Z?Z?(两次8(仅，D=(Q2,1,^))

nq-iBUlBB(3(。2,1)=(0,1,乃)

FBqfllIBB(“2,B)=(b,B,R))

停机状态盯eF,输出为111（一进制）.

19.7（1）在输入符号串的末端增加一个0：

状态集Q={g,4/}

初始状态M

终结状态集尸={盯}

转移函数充

3（^0,0）=（io,。,R）

。（如,1）=（goJD

6（如,8）=（0,0,冗）（在空白处写0,右移停机）

（2）将输入符号串里的最后一个0替换为1：

第19章习题

状态集Q={预,他,0}

初始状态{go}

终结状态集F={0}

转移函数充

6(qo,O)=(go,0,7?)

6(Qo：l)=(qo,l,R)

6(qo,3)=(qi,3,L)(右端左移)

“机,0)=(0,1,&)(替换最右。为1)

J(yi,l)=(gi,l,L)(左移继续查找)

6(gi,B)=(qf,B,R)(无。可替换,停机)

(3)将输入符号串里的所有0都替换为1,1保持不变：

状态集Q={<7o>Qf}

初始状态{<70}

终结状态集F={q/}

转移函数6：

6(®,O)=(qo,l,A)(0替换为1)

讥g,1)=(如,1,4)(1保持不变)

6—)=(q/,B,R)(扫描完成,停机)

(4)在输入符号串的末端增加一个0或1,使得结果中1的个数为偶数：

状态集Q={Qe,ven,{/odd？Qf}

初始状态Qeven(l的个数为偶数)

终结状态集尸={0}

转移函数充

，(qeven：0)=(Sevens0,7?)

((/even,1)=([odd,1,R)

3(qodd,o)=(q°dd,o,A)

6(Qodd,1)=Seven,1,A)

△Seven,B)=(Q/,0,R)(偶数个1,加0)

“q°dd,E)=(0,im)(奇数个1,加1)

⑸将输入符号串中的所有11替换为00：

状态集Q={</0,。1,。2,力}

初始状态M

终结状态集？-{盯}

转移函数6：

5(《),0)=(qo,O㈤

=(<71」,凡)(遇到1,进入内)

15(加,3)=(q“B,R)(扫描完成,停机)

5(qi,0)=(q“0,A)(单个1,继续扫描)

5(d，1)=(仅，0，£)(连续第二个1,替换为0并左移)

d(qi,B)=(qf,B,R)(单个1结尾,停机)

•5(92,1)=(Qo,0,H)(连续第一个1,替换为0)

7

第19章习题

19.8（1）所有以而开头的符号申：

状态集Q={如⑼心切}

初始状态qo

终结状态集尸={盯}

转移函数比

6（qo,a）=（＜7],凡A）

=112、b、R）

6（"a）=（q2MH）

6（位,））=（仪,“R）

6（。2,3）=（qf,B、R）

（2）所有以aa开头,以附结尾的符号串：

状态集Q={%,佻，。2,莪，＜?4朱/}

初始状态qo

终结状态集F={g/}

转移函数比

3（如。）=（qi,o,/?）

“Qi,a）=（M。,A）

火侬。）=（佐凡A）

”02,0）=（Q2,b,R）

6（仅,〃）=（q-3,B,L）

6g3,，）=（q^AL）

6（如））=（q『,hR）

（3）所有不包含aaa子中的符号串：

状态集Q={。0,仇，。2,或，0}

初始状态q。

终结状态集F={%}

转移函数比

B（qo,a）=7?）

3（qoM=（如,“A）

6（%,B）=（w㈤A）

3（qi，a）=（＜72,。，A）

3（qiM=（q°mR）

6（仇㈤=（q「B、R）

6（%Q）=（。3,a,△）