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

332 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13

Fig. 13-4

(b) The state diagramD=D(M)appears in Fig. 13-4(b). Note that the vertices ofDare the states ofM. Suppose

F(si,aj)=(sk,zr). (That is,f(si,aj)=skandg(si,aj)=zr).

Then there is a directed edge fromsitosklabeled by the pairaj,zr. Usually, the input symbolajis put near the

base of the arrow (nearsi) and output symbolzris put near the center of the arrow.

(d) Starting at the initial states 0 , we move from state to state by the arrows which are labeled respectively, by the

given input symbols as follows:

s 0

a

−→s 1

a

−→s 3

b

−→s 2

a

−→s 1

b

−→s 1

a

−→s 3

a

−→s 0

b

−→s 2

b

−→s 0

a

−→s 1

b

−→s 1

The output symbols on the above arrows yield the required output wordv=xyxzzyzxxz.

13.2. LetMbe the finite state machine with input setA={a, b}, output setZ={x, y, z}, and state diagram

D=D(M)in Fig. 13-5(a).

Fig. 13-5

(a) Construct the state table ofM.

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

(a) The state table appears in Fig. 13-5(b). Sinces 0 is the initial state, it is listed first.

Also, F(si,aj)=(sk,zr)if there is a directed edge fromsitosklabeled by the pairaj,zr.

(b) Move from state to state by the arrows which are labeled, respectively, by the given input symbols to obtain the

following output: (i)v=xz^2 x^2 y^2 x; (ii)v=xy^2 xzxx^2 z.

TURING MACHINES

13.3. LetMbe a Turing machine. Determine the pictureαcorresponding to each situation:

(a) Mis in states 3 and scanning the third letter of the tape expressionw=aabca.