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

334 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13

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

We need to find a Turing machineMwhich computesf. Specifically, we wantMto erase all the 1s from〈x〉and

one of the 1s from〈y〉. This is accomplished with the following quintuples:

q 1 =s 01 Bs 1 R, q 2 =s 0 BBs 1 R, q 3 =s 11 BsHR

Hereq 1 erases all the 1s in〈x〉while movingMto the right. WhenMscans the dividing blank B,q 2 changes the

state ofMfroms 0 tos 1 and movesMright. Thenq3 erases the first 1 in〈y〉and haltsM.

SupplementaryProblems

FINITE STATE MACHINES

13.10. LetMbe the finite state machine with state table appearing in Fig. 13-6(a).

Fig. 13-6

(a) Find the input setA, the state setS, the output setZ, and the initial state ofM.

(b) Draw the state diagramD=D(M)ofM.

(c) Find the output wordvif the input is the word: (i)w=ab^3 a^2 ba^3 b; (ii)w=a^2 b^2 ab^2 a^2 b.

13.11. LetMbe the finite state machine with input setA={a, b, c}, output setZ={x, y, z}and state diagram
D=D(M)in Fig. 13-6(b).

(a) Construct the state table ofM.

(b) Find the output wordvif the input is the word: (i)w=a^2 c^2 b^2 cab^3 ; (ii)w=ca^2 b^2 ac^2 ab.

13.12. LetMbe the finite state machine with input setA={a, b}, output setZ={x, y, z}, and state diagram
D=D(M)in Fig. 13-7(a). Find the output wordvif the input is the word:

(a) w=ab^3 a^2 ba^3 b; (b)w=aba^2 b^2 ab^2 a^2 ba^2.

13.13. Repeat Problem 13.12 for the state diagramD=D(M)in Fig. 13-7(b).