The Gateway to Computer Science Excellence
0 votes
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, …….$ 
in Theory of Computation by Boss (30.2k points)
recategorized by | 605 views

1 Answer

+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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,490 answers
195,432 comments
100,656 users