recategorized by
2,068 views
0 votes
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$

  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 by

1 Answer

2 votes
2 votes

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, ....

Answer:

Related questions

3 votes
3 votes
1 answer
1
makhdoom ghaya asked Aug 1, 2016
857 views
Match the following $:$ $\begin{array} {clcl} & \textbf{List – I} && \textbf{List – II} \\ \text{a.}& \text{Context free grammar} & \text{i.} & \text{Linear bounded a...
6 votes
6 votes
7 answers
4