According to pumping lemma for context free languages : Let L be an infinite…
2014
According to pumping lemma for context free languages :
Let L be an infinite context free language, then there exists some positive integer m such that any w ∈ L with | w | ≥ m can be decomposed as w = u v x y z
- A.
with | vxy | ≤ m such that uvi xyi z ∈ L for all i = 0, 1, 2
- B.
with | vxy | ≤ m, and | vy | ≥ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
- C.
with | vxy | ≥ m, and | vy | ≤ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
- D.
with | vxy | ≥ m, and | vy | ≥ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
Attempted by 20 students.
Show answer & explanation
Correct answer: B
Correct statement of the pumping lemma for context-free languages:
There exists an integer m > 0 such that any string w in the language with length |w| ≥ m can be decomposed as w = u v x y z.
The following conditions hold for that decomposition:
|vxy| ≤ m
|vy| ≥ 1 (so at least one symbol is actually pumped)
For every nonnegative integer i (i ≥ 0), the string u v^i x y^i z is in the language.
Brief explanation:
The bound |vxy| ≤ m ensures the pumped region lies within a bounded portion of the parse tree related to the grammar's limited number of distinct variables along a path.
The condition |vy| ≥ 1 ensures pumping is nontrivial (something actually changes when i changes).
Requiring u v^i x y^i z ∈ L for every i ≥ 0 is what allows using the lemma to prove that a language is not context-free by finding a witness string that cannot satisfy this for some i.
Hence the option stating "with |vxy| ≤ m, and |vy| ≥ 1, such that u v^i x y^i z ∈ L for all i ≥ 0" is the correct formulation.