32. State the principle of Pumping Lemma.
If an infinite language is regular,k it can be defined by a DFA. The
DFA has some finite number of states (say n). Since the language is
infinite, some strings of the language should have length >n. For a string
of length >n accepted by DFA, the walk through of the DFA must
contain a cycle. Repeating the cycle an arbitrary number of times should
yield aother string accepted by the DFA.
33. How will you show that a given infinite language is not regular using a
Pumping Lemma?
(i) Assume that the lan guage L is reg u lar
(ii) By Pigeon-hole principle, any sufficiently long string in L
should repeat some state in the DFA, and therefore, the walk
contains a “cycle”.
(iii) Show that repeating the cycle some number of times
(“pumping” the cycle) yields a string that is not in L.
(iv) Conclude that L is not regular.
33. Give the formal definition of a Pumping Lemma.
If L is an infinite regular language, then there exists some positive
integer ‘m’ such that any string w L
∈ , whose length is ‘m’ or greater can
be decomposed into three parts, xyz where
(i) | xy | is less than or equal to m
(ii) | y | > 0,
(iii) w xy z
i
i
=
is also in L for all i = 0 1 2 3
, , , , KK
34. Is the language L a b n
n n
=
≥
{
:
}
0 regular or not.
The language L is not regular.
35. Are the following languages regular or not.
(a) L a b n k
n
n k
=
>
≥
{
:
}
and
0
(b) L a n
n
= { : is a prime number}.
(a) Not reg u lar
(b) Not regular.
36. State the closure property of Regular Languages.
(a) If L 1 and L 2 are reg u lar over Σ, then L
L
1
2
∪ is reg u lar, i.e.,
union of two reg u lar sets is also reg u lar. Reg u lar sets are
closed w.r.t. union.
(b) If L 1 and L 2 are regular, so is L
L
1
2
∩ , i.e., regular sets are
closed w.r.t. intersection.
37. State the Myhill-Nerode Theorem.
Let R ⊆ Σ
* . The following statements are equivalent
(i) R is reg u lar
DFA and NFA
113