Mathematical Foundation of Computer Science

DHARM

172 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

7.2.2 Representation of a DFA

Obviously, A Deterministic Finite State Automata has a finite set of states and the transition
between states are defined to a set of states over a set of input symbols, which returns a set of
states. We can represent the DFA either through states diagram and through transition table.
7.2.2.1 In state diagram, we use following convention;
l A state is shown by a circle, suppose p is a state then it is represented as,

p

l The transition between states shown by an arc between them which is loaded by

input symbol with direction mark by an arrow, for example

δ (q, a) = p is represented as,

q a q

where p and q are states and the arc loaded with input symbol a shows the transition from
state q to state p.
l Start (initial) state is marked by an start arrow, for example if state q is the start
state then it is represented as,

q

l Final/Accepting state is marked by double circle, for example if state p is the final/

accepting state then it is represented as,

p

Example 7.1. A DFA M = (Q, Σ, δ, q 0 , F) has Q = {q 0 , q 1 }, Σ = {a, b}, F = {q 1 } and q 0 is the initial
state 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 ;
The transition diagram of above DFA M is shown below (Fig. 7.4)

q 0 q 1

a

a

b

b

Fig. 7.4
Note: From DFA we see that there is exactly one and only one transition (exit arc) from each state
on each input symbol so the automaton M is ‘Deterministic’ (DFA). Conversely, if the finite automata have
more than one transition/s (exit arc) from a state on single/same symbol then automata is
‘Nondeterministic’ (NFA).