Mathematical Foundation of Computer Science

DHARM

248 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Hence, we prepare a transition function table III for Moore machine.

Table III

State

Input symbol

a

[A, 0]

b

[A, 1]

[B, 0]

[B, 1]

[C, 0]

[C, 1]

[D, 1]

[D, 1]

[A, 0]

[A, 0]

[D, 0]

[D, 0]

[C, 0]

[C, 0]

[B, 1]

[B, 1]

[A, 1]

[A, 1]

[D, 1]

[D, 0]

[B, 1]

[B, 1]

[D, 0]

[D, 0]

Since we assume that [A, 0] is the start state of the Melay machine so it is marked by an
arrow in the transition table. The state diagram of the Moore machine shown in Fig. 9.44.

[A, 0]

[A, 1] [B, 1]

[B, 0]

[C, 1]

[C, 0]

[D, 1]

[D, 0]

a

a a b

a

a

a

b

b

a

a

b

b

b

b

b

Fig. 9.44 Moore machine.

EXERCISES

9.1 Write regular expressions for each of the following languages over the alphabet {0, 1}.

(i) The set of all strings containing at least of two 0’s.

(ii) The set of all strings not containing 001 as a substring.

(iii) The set of all strings with an equal number of 0’s and 1’s.

(iv) The set of all strings of odd length.

(v) The set of all strings containing of both 100 and 011 as substrings.