For Σ = {𝑎, 𝑏}, let us consider the regular language 𝐿 = { 𝑥 |𝑥 = 𝑎2+3𝑘 or 𝑥 = 𝑏10+12𝑘, 𝑘 ≥ 0}. Which one of the following

Q. For Σ = {𝑎, 𝑏}, let us consider the regular language 𝐿 = { 𝑥 |𝑥 = 𝑎^2+3𝑘 or 𝑥 = 𝑏^10+12𝑘, 𝑘 ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for 𝐿 ?

(A) 3

(B) 5

(C) 9

(D) 24

Ans: 24

Solution:

According to Pumping lemma, there must be repetition (DFA then it repeats some states, and regular grammar repeats its nonterminal in derivation.) for all acceptable stings. Therefore, minimum Pumping Length should be 11, because string with length 10 (i.e., w = b10) does not repeat anything, but string with length 11 (i.e., w = b11) will repeat states. Therefore, pumping length for given language should greater than 10, which is 24. Option (D) is correct.