(c) Set of strings having ‘aaa’ as a subword.
(d) Set of integers.
Alphabet Σ = {
, }
0,1, K 9
(e) Set of signed Integers.
1.2 NON-DETERMINISTIC FINITE AUTOMATA (NFA)
Def i ni tion
A Nondeterministic Finite Automata (NFA) is defined by a 5-tuple
M
Q
q F
= ( , , , , )
Σ δ 0
where Q
q F
, , , ,
Σ δ 0
are defined as fol lows:
Q = Finite set of inter nal states
Σ = Finite set of sym bols called “Input alpha bet”
δ = Q
Q
× ∪
→
(
{ })
Σ
λ
2
q Q
0 ∈ is the Ini tial states
F Q
⊆ is a set of Final states
NFA differs from DFA in that, the range of δ in NFA is in the powerset 2
Q .
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.
Ì Exam ple 1.2.1: Obtain an NFA for a language consisting of all strings
over {0,1} containing a 1 in the third position from the end.
Solu tion
q 1 , q 2 , q 3 are initial states
70
Theory of Automata, Formal Languages and Computation
q 0
q 1 0-9
1-9
q 0
q 1
0-9
q 2
+,–
1-9
q 0
q 1
q 2
q 3
a
a
a
b
b
b
b
a