UGCNET CSE December 2022: 30

Question

 

In Pumping Lemma for regular languages, to say a language is satisfying pumping lemma, what is the minimum length of ' $\text{y}$ ' if you consider the string as ' $\text{xyz}$ '.

1. $\mathrm{n}$
2. $2$
3. $1$
4. $0$

(Option $1 [39417]) 1$
(Option $2 [39418]) 2$
(Option $3 [39419]) 3$
(Option $4 [39420]) 4$

Answer Given by Candidate : $2$

Answer 1

The question is about the Pumping Lemma for regular languages. In the Pumping Lemma, for a regular language L, there exists a pumping length p (or often denoted as n in some texts) such that any string s∈L with ∣s∣≥p can be divided into three parts, s=xyz, satisfying three conditions:

1. ∣xy∣≤p (or ∣xy∣≤n)

2. ∣y∣≥1

3. For all i≥0, xy^iz∈L

The question asks for the minimum length of 'y' if you consider the string as 'xyz'.

According to the second condition, ∣y∣≥1. This means the length of the substring 'y' must be at least 1. It cannot be zero because then pumping (repeating 'y') would have no effect on the string, which defeats the purpose of the lemma.

Therefore, the minimum length of 'y' is 1.

The final answer is 3​