- Home
- Theory of Computation
- Regular Languages and Finite Automata
- Regular Languages
- Pumping Lemma For Regular Languages

For Σ = {a, b}, let us consider the regular language L = {x|x = a^{2+3k} or x = b^{10+12k} k ≥ 0}.

This question was previously asked in

GATE CS 2019 Official Paper

- 3
- 5
- 9
- 24

Option 4 : 24

Free

IBPS SO IT Officer Mains: Full Mock Test

4812

60 Questions
60 Marks
45 Mins

Regular language L = {x|x = a^{2+3k} or x = b^{10+12k} k ≥ 0}.

L = {a^{2}, a^{5}, a^{8}, a^{11} … ∪ b^{10}, b^{22}, b^{34}…}

**Pumping Lemma:**

Let L be an infinite regular language. Then there exists some positive integer m such that any w ϵ L with |w|≥ m can be decomposed as

w = xyz

with |xy|≤ m such that w_{i} = xy^{i}z

is also L for all i = 0, 1, 2, …

Therefore, minimum Pumping Length should be 11, because string with length 10 (i.e., w = b^{10}) does not repeat anything, but string with length 11 (i.e., w = b^{11}) will repeat states.

Hence option 1, 2, and 3 are eliminated.

Therefore 24 can be the pumping lemma length.
India’s **#1 Learning** Platform

Start Complete Exam Preparation

Daily Live MasterClasses

Practice Question Bank

Mock Tests & Quizzes

Trusted by 2,16,64,244+ Students

Start your FREE coaching now >>

Testbook Edu Solutions Pvt. Ltd.

1st & 2nd Floor, Zion Building,

Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

[email protected]
Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

Toll Free:1800 833 0800

Office Hours: 10 AM to 7 PM (all 7 days)