605 views

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 \in L$ with $| w | \geq m$ can be decomposed as $w = u v x y z$

1. With $| vxy | \leq m$ such that $uv^{i}xy^{i} z\in L$ for all $i = 0, 1, 2$
2. With $| vxy | \leq m$, and $| vy | \geq 1$, such that $uv^{i}xy^{i} z\in L$ for all $i = 0, 1, 2, …….$
3. With $| vxy | \geq m$, and $| vy | \leq 1$, such that $uv^{i}xy^{i} z\in L$ for all $i = 0, 1, 2, …….$
4. With $| vxy | \geq m$, and $| vy | \geq 1$, such that $uv^{i}xy^{i} z\in L$ for all $i = 0, 1, 2, …….$

recategorized | 605 views

+1 vote

ans is B

context-free pumping lemma to be the following. Let L be an infinite context-free language. Then there exists some positive integer m such that any w that is a member of L with |w| ≥ m can be decomposed as

w = uvxyz,

with  |vxy| ≤ m, and |vy| ≥ 1,

such that wi = uvixyiz,

is also in L for all i = 0, 1, 2, ....

by Boss (48.8k points)