Chapter 3: The Theory of Automata g 103
SELF-TEST
Study the automaton given in Fig. 3.20 and choose the correct answers
to Questions 1-5:
-iGJpo
1,/-\
/
\
oc£5 1 .8Jo
Fig. 3.20 Automaton for Questions 1-5
1. M is a
(a) nondeterministic automaton
(b) deterministic automaton accepting {O. I} *'
(c) deterministic automaton accepting all strings over {O, I} having
3m O's and 3n ]'s, m. 11 2 1
(d) detelministic automaton
2. M accepts
(a) 01110
(b) 10001
(e) 01010
(d) 11111
3. T(M) is equal to
(a) {03111 1
311 1m. 11 2 O}
(b) {O'm 1
311
Im. n 2:: I}
(e) {1\ IH' has III as a substring}
(d) {H IH' has 31i l·s. 11 2 I}
4. If q2 is also made a final state. then At accepts
(a) 01110 and 01100
(b) 10001 and 10000
(c) 0110 but not 0111101
(d) 0
311 • 11 2:: 1 but not 1
311 • 11 2:: 1
5. If q: is also made a final state, then T(M) is equal to
(a) {0
3111 1
3
/1 I In, 11 2 O} u {0
2111 1" I m, 11 2 O}
(b) {03m 1
3n
I m. Ii 2 I} u {O:'" I" I m. 11 2:: I}
(c) {H' IH' has III as a substring or 11 as a substring}
(d) {w I the number of l's in ]V is divisible by 2 or 3}
Study the automaton given in Fig. 3.21 and state whether the Statements
6-15 are true or false:
0.1
0,1
@1---O-'~0
Fig. 3.21 Automaton for Statements 6-15