DHARM186 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
Therefore, the only acceptable path from starting state q 0 is shown by dark line. Along
to this path NFA N reaches to the acceptable state q 3 at the end of the string 101101.
7.3.5 Language of an NFA
After determine the behavior of the NFA over an arbitrary string, we can easily define the
language of a NFA. Let N be a NFA i.e., N = (Q, Σ, δ, q 0 , F), then language accepted by NFA is
LN, where,
LN = {x/x ∈ Σ and δ$(q 0 , x) ∈ P(Q) s.t. δ$(q 0 , x) ∩ F ≠ Φ}
It means, language LN contains an arbitrary string x, chosen from the set of possible
strings Σ such that NFA N, after reading the string x (from the initial state q 0 ) reaches to the
state that is in power set of Q, such that its relation with set F is not disjoint. That is, at least
one state is common between set F and P(Q).
Example 7.12. From the NFA given in example 7.11, test the string 10101 whch is not in the
language of N.
Sol. Assign string 10101 to x, if x is a language of N (where x ∈ Σ*, i.e., Σ = {0, 1}), then after
reading the string x, NFA N reaches to its final state, i.e. any state that belongs to the power
set of Q which contains the final state {q 3 }. Now we can construct the moves of NFA over the
string x = 10101, that is shown in Fig. 7.22.
1
q 0 []¹q 3
0
1
010
Fq 0 q 0 q 0 q 0 q 0q 1 q 2 []¹q 3q 1 q 201 0 1[]¹q 3
Fig. 7.22
Since, δ^ (q 0 , 10101) = Φ or {q 0 } or {q 2 }, so none of the set contains state {q 3 }. Hence, δ^(q 0 ,
10101) ∩ {q 3 } = Φ. It concludes that string 10101 is not accepted by NFA N.
EXERCISES
7.1 Construct the DFA, which accept the following languages over {0, 1} :
(i) The set of all strings with two consecutive 0’s.
(ii) The set of all strings ending with 101.
(iii) The set of all strings that begin with 0 and ending with 01.
(iv) The set of all strings in which no 0 is followed immediately by 1.
7.2 Construct the NFA to accept the languages given in the example 7.1.
7.3 Describe the language accepted by the following finite automatons.
(i)AAB
BBA$ #State Input SymbolInputSymbol (ii)PQP
QRP$ #State Input SymbolInputSymbolRRR