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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,490 answers

195,432 comments

100,656 users