Mathematical Foundation of Computer Science

DHARM

174 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

q 0 q 1

a

a

q 2

1

4

(^2) b
3
b
Fig. 7.6

2. If there is a string containing symbol a followed by one b (arrow 2) then it reaches to
   q 2 which is an accepted state. It is also true for a’s, 3a’s, 5a’s ....followed by b’s, 3b’s,
   5b’s, .... (Fig. 7.6)

q 0 q 3

b

b

q 2

5

6

(^7) a
8
a
Fig. 7.7

3. If string contains First symbol b (arrow 5) then next state (q 3 ) onwards there must
   be remaining symbols in the string is odd numbers of a’s (1,3,5...) with even no. of b’s
   (2, 4, 6) s.t. all a’s in the string become odd, (Fig. 7.7).


4. If there is a string containing First symbol b (arrow 5) followed by one a then (arrow 7)
   it must reach to an accepted state (true for odd no. of a’s and b’s) (Fig. 7.7).


5. Combining Fig. 7.6 and Fig. 7.7 we get the final DFA that is shown in Fig. 7.8. So the
   DFA M for the above language is represented as,
   M = ({q 0 , q 1 , q 2 , q 3 }, {a, b}, δ, q 0 , {q 1 })

q 0

q 3

b

b

q 2

a

q 2

a

a

a

b

b

Fig 7.8

7.2.2.2 Transition Table

In spite of complex transition diagram for many DFA’s there is a simpler representation of
transition functions by a table. In the table entries, rows contain all the states of the set Q and
columns contain all the input symbols of set S.