Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

336 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13

13.24. Letf be the functionf (n)=n−2 whenn>1 andf (n)=0 whenn=0 or 1. Show thatf is
computable.

13.25. Letfbe the functionf (x, y)=x. Show thatfis computable.

Answers to Supplementary Problems

13.10. (a)A=(a, b),S={s 0 ,s 1 ,s 2 },Z={x, y, z}, ands 0

is the initial state. (b) See Fig. 13-8(a).

(c)v=y^2 zyzxzxyz.

13.11. (a) See Fig. 13-8. (b) (i)v=xyz^2 x^2 zx^3 z^2 ,

(ii)v=xy^2 xz^3 xyx.

13.12. (a)xy^3 zxyzxz^2 ; (b)xyzxy^2 z^2 x^2 z^2 y^2.

13.13. (a)zyz^2 xy^2 xyzy; (b)zyxy^2 zx^2 zxy^2 xy.

13.14. (a)α=abs 2 baa; (b)α=aabs 3 b; (c)α=s 0 aaabbb;

(d)α=s 01111 B111.

13.15. (a)β=abbs 3 a; (b)β=as 3 baa; (c)β=abbs 2 a;

(d)β=as 3 bba; (e)αa is not changed byq;

(f)β=as 2 baa.

13.16. (a)β=bs 1 Bab; (b)β=s 3 BaBab;(c)β=bs 2 Bab;

(d)β=s 3 BbBab; (e)αis not changed byq;

(f)β=s 2 BaBab.

13.17. α 1 =s 0 ab,α 2 =bs 1 b,α 3 =s 2 bb,α 4 =as 3 b;

q 1 =s 0 abs 1 R,q 2 =s 1 bbs 2 L,q 3 =s 2 bas 3 R,

q 4 =s 3 bbs 0 L.

13.18. Yes.

13.19. No, sinceα→β→α→β→α→β→ ···

never ends.

13.20. q 1 =s 0 BBsNR(NO);q 2 =s 0 bbsNR(NO);

q 3 =s 0 aas 1 R;q 4 =s 1 BBsNR(NO);q 5 =s 1 aasNR

(NO);q 6 =s 1 bbsNR;q 7 =s 2 bbs 2 R;q 8 =s 2 aasNR

(NO);q 9 =s 2 BBsYR(YES).

13.21. q 1 =s 0 BBsNR(NO);q 2 =s 0 bbsNR(NO);

q 3 =s 0 aas 1 R;q 4 =s 1 BBsYR(YES);

q 5 =s 1 bbsNR(NO);q 6 =s 1 aas 2 R;q 7 =s 2 BBsYR

(YES);q 8 =s 2 aasNR(NO);q 9 =s 2 bbsNR(NO).

13.22. (a)〈 6 〉= 17 ; (b)〈m〉= 16 B 1 B 14 B 12 ;

(c)〈m〉= 1 B 1 B1; (d) not defined.

13.23. (a)[E]=7; (b)[E]=2; (c)[E]=14.

13.24. Strategy: Erase first three 1s

q 1 = S 01 Bs 1 R;q 2 = s 1 BBsHR(HALT);q 3 =

S 11 Bs 2 R;q 4 =s 2 BBsHR(HALT);q 5 =s 2 BBsHR

(HALT).

13.25. Strategy: Erase first 1 and then all 1s afterB.

q 1 = s 01 Bs 1 R;q 2 =S 111 s 1 R;q 3 =S 1 BBs 2 R;

q 4 =S 21 Bs 3 R;q 5 = S 31 Bs 3 R;q 6 =S 3 BBsHR

(HALT).

Fig. 13-8