UGC NET CSE | December 2013 | Part 3 | Question: 40

Question

Pumping lemma for context-free languages states:

Let $L$ be an infinite context free language. Then there exists some positive integer m such that any $w \in L$ with $\mid w \mid \geq m$ can be decomposed as $w=uv \, xy \, Z$ with $\mid vxy \mid$ ______ and $\mid vy \mid$ ________ such that $uv^{\dot{z} } xy^{\dot{z}} \, Z \in L$ for all $\dot{z} = 0, 1, 2 ,\dots$

• A. $\leq m, \leq 1$
• B. $\leq m, \geq 1$
• C. $\geq m, \leq 1$
• D. $\geq m, \geq 1$

Answer 1

Let L be an infinite context-free language. Then there is some positive integer m such that, if S is a string of L of length at least m, then

• S = uvwxy (for some u, v, w, x, y)
• |vwx|  m
• |vx|  1
• uvⁱwxⁱy  L

for all nonnegative values of i.

B is ans.

Comments

Please explain in easy language what does this mean

Answer 2

ans is B ≤m,≥1 ≤m,≥1

If a language L is context-free, then there exists some integer m ≥ 1 (called a "pumping length"^[1]) such that every string s in L that has a length of m or more symbols (i.e. with |s| ≥ m) can be written as

s = uvwxy

with substrings u, v, w, x and y, such that

1. |vwx| ≤ m,

2. |vx| ≥ 1, and

3. uvⁿwxⁿy is in L for all n ≥ 0.

Below is a formal expression of the Pumping Lemma.

∀L⊆Σ^*. (context_free(L) ⇒ ∃m≥1. ∀s∈L. (|s|≥m ⇒ ∃u,v,w,x,y∈Σ^*. (s=uvwxy ∧ |vwx|≤m ∧ |vx|≥1 ∧ ∀n≥0. uvⁿwxⁿy∈L)))