Mathematical Foundation of Computer Science

DHARM

INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 177

Example 7.5. Give a DFA that accepts the language over alphabet a and the string contains
zero/multiples of 4 a’s. Or,
Construct the DFA that accepts the strings of the set {∈, aaaa, aaaaaaaa, ......}.
Sol. Let M be a DFA and {q 0 } is the initial state.
I. If first symbol is null string (∈) then initial state (q 0 ) is the final state also so state diagram
will be,

q 0

II. From the state q 0 onwards there is a consumption of 4-consecutive a’s followed by none/

more such sets of a’s, i.e.,

q 0 q 1 q 2 q 3

aaa

a

Fig. 7.12

So the final DFA M is ({q 0 , q 1 , q 2 , q 3 }, {a}, δ, q 0 , {q 0 }) shown in Fig. 7.12; and the transition

function δ is shown in the transition table in Fig. 7.13.

State

Input symbol

a

q 1

q

q

q

2

0

0

q

q

q

q

0

1

2

3

Fig. 7.13

7.2.3 δ-head

Instead of defining the behavior of transition function over a single symbol (alphabet), which
is a mapping of a state with a input symbol and returns a state i.e., δ: Q × S → Q, it is also
required to know the behavior of the transition function over an arbitrary string (s. t. au-
tomata not only read a single symbol but a sequence of symbols or string)) such characteristics
include in the definition of δ-head.
7.2.3.1 Definition
Assume, if a string is defined over set of alphabet Σ then set of possible string is in Σ, then δ-
head is defined as:
δ$^ : Q × Σ →^ Q
or we say that δ-head is the transition function that map a state(∈ Q) with a string (∈ Σ* ) and
returns a state (∈ Q).