(b) Non-deterministic Automata
3. What do you mean by deterministic automata?
If the internal state, input and contents of storage are known, it is
possible to predict the future behaviour of the automaton. This is said to
be deterministic automaton.
4. What do you mean by non-deterministic automata?
If the internal state, input and contents of storage are known, if it is
not possible to predict the future behaviours of the automaton, it is said
to be non-determine automaton.
5. Give the formal definition of Deterministic Finite Automaton (DFA).
A Deterministic Finite Automaton (DFA) is a t-tuple
M
Q
q F
= ( , , , , )
Σ δ 0
where
Q = Finite state of “internal states”
Σ = Finite state of symbols called ‘Input Alphabet’.
δ :Q
Q
× →
Σ
= Transition function
q Q
0 ∈ = Initial state
F Q
⊆ = Set of Final states.
6. Define the transition function δ in DFA.
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 .
7. Give the formal definition of Non-deterministic Finite Automata
(NFA).
A non-deterministic Finite Automata (NFA) is defined by a 5-tuple
M
Q
q F
= ( , , , , )
Σ δ 0
where Q
q F
, , , ,
Σ δ 0 are defined as follows:
Q = Finite set of internal states
Σ = Finite set of symbols called ‘Input alphabet’
δ
λ
= × ∪
→
Q
Q
(
{ })
Σ
2
q Q
0 ∈ is the ‘Initial state’
F Q
⊆ is a set of Final states.
8. What is the difference between NFA and DFA in terms of the transition
function δ?
NFA differs from DFA is that, the range of δ in NFA is in the
powerset 2
Q .
9. When is a string accepted by an NFA?
A string is accepted by an NFA if there is some sequence of possible
moves that will put the machine in the final state at the end of the string.
DFA and NFA
109