The Gateway to Computer Science Excellence

0 votes

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$

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

+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 *w _{i}* =

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

52,345 questions

60,497 answers

201,859 comments

95,315 users