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

52,215 questions

59,993 answers

201,197 comments

94,663 users