An automaton whose output response is “yes” or “No” is called an
“Acceptor”.
1.1.3 Def i ni tion of Deter min is tic Finite Autom a ton
A Deterministic Finite Automator (DFA) is a 5-tuple
M
Q
q F
= ( , , , , )
Σ δ 0
where
Q
= Finite state of “internal states”
Σ
= Finite set of symbols called “Input alphabet”
δ :Q
Q
× →
Σ
= Transition Function
q Q
0 ∈
= Initial state
F ⊆ Q
= Set of Final states
The input mechanism can move only from left to right and reads exactly
one symbol on each step.
The transition from one internal state to another are governed by the
transition function δ.
If δ( , )
,
q a q
0
1
=
then if the DFA is in state q 0 and the current input symbol
is a, the DFA will go into state q 1 .
Ì Exam ple 1.1.1: Design a DFA, M which accepts the language
L M
w a b w
( ) {
( , ) :
*
= ∈
does not contain three consecutive b’s).
Let
M
Q
q F
= ( , , , , )
Σ δ 0
where
Q = {q 0 , q 1 , q 2 , q 3 }
Σ = {a, b}
q 0 is the initial state
F = {q 0 , q 1 , q 2 ,} are initial states
and δ is defined as follows:
Ini tial state
q
Sym bol
σ
Final state
δ σ
( , )
q
q 0
a
q 0
q 0
b
q 1
q 1
a
q 0
q 1
b
q 2
q 2
a
q 0
q 2
b
q 3
q 3
a
q 3
q 3
b
q 3
DFA and NFA
59