382 .\;!, Solutions (or Hints) to Chapter-end Exercises
3.3 Both the strings are not accepted by M.
3.4 As b(q!, a) = b(q[, a), R is reflexive. Obviously it is symmetric.
If q!Rq2, then b(q[, a) = b(q2, a).
If q2Rq3 then b(q2' a) = b(q3, a). Thus b(q[, a) = b(q3' a), implying
that q!Rq3' So R is an equivalence relation.
3.5 The state table of NDFA accepting {ab, ba} is defined by Table A3.1.
TABLE A3.1 State Table for Exercise 3.5
StatelI.
a
b
The state table of the corresponding DFA is defined by Table A3.2.
TABLE A3.2 State Table of DFA for Exercise 3.5
StatelI.
[qo]
[q1]
[q2]
~
o
a
b
3.6 The NDFA accepting the given set of strings is described by
Fig. A3.1. The corresponding state table is defined by Table A3.3.
a, b
Fig. A3.1 NDFA for Exercise 3.6.
TABLE A3.3 State Table for Exercise 3.6
State/I.
a
b
qo
qo- q1
qo
q1
q2
q2
q3
q3
The DFA accepting the given set is defined by Table A3.4.