Mathematical Foundation of Computer Science

DHARM

INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 171

movement is restricted only in forward/ right direction. Once it moves forward it never returns
back or left. Suppose Automata M initially (time t = 0/no time) on state q 0. Tape head reads
currently pointing symbol a, and automata goes to next state q 1. Now the tape head pointed to
the symbol b. Now automata reads the symbol b and goes to next state q 2 (Fig. 7.2). In this way
automaton scans all the entries of the tape cells and reaches to the last cell. We assume that,
after time t automaton M reaches to final state (qf ) after scanning the whole tape and it stops
(never moves).

a bbb... aa

T

H

DFA

M

q 1

a bb

T

H

DFA

M

q 2

a bb

T

DFA H

M

qf

b ... aa

ÞÞ

b ... aa

Fig. 7.2
So, after scanning the whole tape entries that contains the string, automaton M goes in
the state, which is final state, it means the string is accepted by the machine M otherwise
string is rejected by M (it means automata M not reaches to its end state while scanning the
whole string). These possible outcomes of a DFA are shown in Fig. 7.3.

Yes (String is Accepted)

String

No (String is Rejected)

M

Fig. 7.3

7.2.1 Definition

A deterministic finite state automata (DFA) has:
· A finite set of states Q
· A finite set of input symbols Σ
· A transition function δ†, which defines the next transition (move) over an input symbol
· A start state q 0 , where q 0 ∈ Q (any one of the state in the set Q is a start state).
· A set of accepting state (final state) F. One or more state/s may acts as final state/s,
which is certainly a subset of Q or F ⊆ Q.
So, a DFA M is defined by above discussed 5-tuples as:
M = (Q, ΣΣΣΣΣ, δδδδδ, q 0 , F)

†The Transition function δ is truly a mapping of a state (∈ Q) with an input symbol
(∈ Σ) and returns to a state (∈ Q) or,
δ: Q × Σ → Q
For example, if q is a state (∈ Q) and a symbol a (∈ Σ) that returns state p(∈ Q), then transition
function δ is,
δ (q, a) → p
Or, automata M is in state q and after reading an input symbol a M moves on next state p. State
p may be same as q means automata remains in its state on consuming the input symbol, i.e.,
δ (q, a) → q