Mathematical Foundation of Computer Science

DHARM

INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 173

Example 7.2. A Deterministic Finite Automata M = (Q, Σ, δ, q 0 , F) has set of states Q = {q 0 , q 1 },

set of input symbols Σ = {a, b}, initial state = {q 0 } and the set of final state F contain a single

state q 0 i.e., F = {q 0 } where F ⊆ Q and the transition function δ is defined as:

δ (q 0 , a) = q 1 ; δ (q 0 , b) = q 0 ; δ (q 1 , a) = q 0 ; δ(q 1 , b) = q 1 ;

q 0 q 1

a

a

b b

Fig. 7.5
The transition diagram of M is shown in Fig. 7.5. Here q 0 is the initial state marked by
arrow and it is also a final state marked by double circle. From given transition function δ of
M, following conclusions will be drawn:
lInitial state is the final state; it means that there is no transition or the transition on
no input symbol which is impossible. For this purpose we assume a special string
called epsilon (∈) i.e.,δ (q 0 , ∈) = q 0 : state remains unchanged.
Hence, string ∈ is accepted by M.
or, lAny string containing one/more symbols of b is also accepted i.e., {b, bb, bbb...}
or, lIf string contains a symbol a then it must contain another symbol a, so that automa-
ton M returns to its final states q 0 , i.e., accepting strings are {aa, aaaa, aaaaaa,
...........}.
or, lif starting symbol is zero/one/more b then accepting strings are:
{aa, aaaa, aaaaaa, .......} or {baa, baaaa, baaaaaa, .......} or
{bbaa, bbaaaa, bbaaaaaa, ......} or { .... .... .... ......}
or { bb.....baa, bb....baaaa, bb....aaaaaaa, .......}
or, lif any number of symbols b lies in between of a i.e., the accepting strings are:
{aba, abba, ......, abababa, abbabbabba, .......,abababababa,
abbabbabbabbabba, ......, abb...babb..babb..ba.........ba }
So, we conclude that any string containing even number of a’s is accepted by M. Hence,
following set of strings is accepted by given DFA M
{∈, b, bb, bbb, ..........., aa, aaaa, ......., aba, abba, ......., abababa...........}
Example 7.3. Design a DFA that accepts the string of odd number of a’s and b’s (both).
Sol. Let DFA M = (Q, Σ, δ, q 0 , F), where Σ = {a, b}, A finite set of states Q is assumed as {q 0 , q 1 ,
q 2 , ...... qi), where q 0 is the initial state, and one/more state(s) assumed ∈ F those are final
state(s).

1. If string containing Ist symbol is a (arrow 1) then next state onward there must
   be odd number of b’s (1, 3, 5...) with even numbers of a’s (2, 4, 6......) such that all
   a’s are odd. (Fig. 7.6)