GATE CSE 2019 | Question: 15

Question

For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ?

• A. $3$
• B. $5$
• C. $9$
• D. $24$

Answer 1

Pumping Lemma for Regular Languages:
For any language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uviw ∈ L
We have to find "n" which satisfies for all the strings in L.
Considering strings derived by b10+12k.
The minimum string in L = "bbbbbbbbbb" but this string b10 cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts "uvw" must be greater than 10 .

Comments

Kindly add one more line "this string b^10 cannot be broken down in uvw such that U V^i w belongs to L"

Answer 2

Pumping length is the minimum length, after which every string can be can be considered a combination (xyz), such that x,y and z are any strings belonging to our language.

For example: For above language consider string: a¹¹

a¹¹ can be written as : a⁵a²a²a²

So here x: a⁵ y: a² z: a²

So we can write above string as : xyyz

Note: we can not convert any of the possible combinations of a^n, where n<11 into above mentioned combination.

Basically, pumping length is the length after which we can accept the strings simply by repeating on the states.

So for length of 11 we require a 12 state DFA.

This will be valid for both a and b.

(You can construct and check it)

So basically here my pumping length would be 11 or any value greater than 11.