The Gateway to Computer Science Excellence

0 votes

Prove the following stronger form of the pumping lemma, where in both pieces $v$ and $y$ must be nonempty when the string $s$ is broken up$.$If $A$ is a context-free language, then there is a number $k$ where, if $s$ is any string in $A$ of length at least $k,$ then $s$ may be divided into five pieces$, s = uvxyz,$ satisfying the conditions$:$

- for each $i\geq 0,uv^{i}xy^{i}z\in A,$
- $v\neq\epsilon$ and $y\neq\epsilon,$and
- $\mid vxy\mid\leq k.$

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- 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.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,154 answers

193,758 comments

93,725 users