Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 255

followed by substring w then we always locate a middle substring v (in between of length n)
that contains at least a symbol (or nonempty) can be ‘pump’ zero/more (finite) times causes the
resulting string returns in language L.
Proof. For proving above lemma we assume that there is a DFA of n distinct states that
accept the regular language L. Let string Z is of k symbols where k ≥ n then string Z can be
written as,
Z = a 1. a 2. a 3. a 4 ......ak.
i.e., | Z | = k so | z |≥ n.
Since we assume that k = n so a DFA accepting the string Z must have following possi-
bilities,
l Either, it is a n state DFA i.e., if one symbol corresponds to one transition arc and if
string contains k symbols where k = n (take one such case), then the string Z = u.v.w
where | Z | = n, is accepted.
Or
l For accepting the string of length ≥ n, an n state DFA must has one/more repetitive
transition arcs on few intermediate states.
Let DFA operates over states set Q where Q contains start state q 0 and other states q 1 ,
q 2 , q 3 ,......,qm where qm ∈ F. Then after consuming string a 1 .a 2 .a 3 .a 4 ...ak, the path taken by
DFA is as follows,
a 1 a 2 a 3 ai+1 aj am
q 0 → q 1 → q 2 → ...... qi → qi+1 ...... qj–1 → qj ...... qm–1 → qm
Since, | Z | ≥ n , or number of symbols in string Z is more than m ( number of states) so
there must be at least one duplication of states. In other words at least two states must be
same (Fig. 10.1). Assume states qi and qj are same thus there exists at least one symbol in
between ai and aj i.e., | v | ≥ 1. The discussed situation is shown below.

(a .a .a a ). (a .... a ). (a ....a )1 2 3.... i i+1 j j+1 k

uv()¹ Î w

because of same states of qi and qj

ai+2 qi– 1

qi+ 1 aj

ai+1

qqii=

qqqj+1–.......... m 1 ® m

am

q 0 ®®®qq 12

a 1 a 2 a (^3) q
i–1
Fig. 10.1
The states diagram of DFA M is shown in Fig. 10.2.
q 0 u qi w qm
v
M
Fig. 10.2