Question

Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?

(a) uv^nwx^ny

(b) uv^nw^nx^ny

(c) uv^2nwx^2ny

(d) All of the mentioned

I had been asked this question in an interview for job.

This interesting question is from Pumping Lemma for Context Free Language in division Properties of Context Free Languages of Automata Theory

Answer 1

Correct answer is (b) uv^nw^nx^ny

The best explanation: Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying |t| >=n, there are strings u, v, w, x, y and z satisfying

t=uvwxy

|vx|>0

|vwx|<=n

For any m>=0, uv^nwx^ny ∈ L