Discrete Mathematics for Computer Science

Exercises 593

Draw the state diagram for the automata. Determine which of the following words are

in the language:

(a) 0011011

(b) 110 110 1

(c) 1111000011110

2. Let E = {0, 11 and Q = {qo, ql, q2}. qo is the start state, and {qj} is the set of accept-
   ing states. The function 8 is defined as
   8 qo ql q2
   0 ql ql q2
   1 q2 q2 qo

Draw the state diagram for the automata. Determine which of the following words are

in the language:

(a) 0011011

(b) 1 101101

(c) 1111000011110

3. Let Z = {a, b, c) and Q = {qo, qI, q2, q3}. qo is the start state, and {ql} is the set of
   accepting states. The function 8 is defined as

8 qo qj q2 q3

a ql q2 q3 qo

b q2 q3 qo qj

c ql qo q3 q2

Draw the state diagram for the automata. Determine which of the following words are

in the language:

(a) acbaccabb

(b) babacacbcca

(c) cbaccbbababc

4. Let E = {a, b, c} and Q = {qo, ql, q2, q3}. qo is the start state, and {qj, q2} is the set

of accepting states. The function (^8) is defined as
8 qo qj q2 q3
a qj q2 q2 q0
b q2 ql qo q'
c ql qo q3 q3
Draw the state diagram for the automata. Determine which of the following words are
in the language:
(a) acbacbbcabb
(b) cbababcacabcca
(c) bbbcbaccbbababc

5. In the transmission of a string of binary digits, three consecutive l's being received is

an indication of an error in the transmission. Define an automata that will detect this

error condition. Draw the state diagram for the automata you define.