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

  1. for each $i\geq 0,uv^{i}xy^{i}z\in A,$
  2. $v\neq\epsilon$ and $y\neq\epsilon,$and
  3. $\mid vxy\mid\leq k.$ 
in Theory of Computation by Boss
edited by | 82 views

Please log in or register to answer this question.

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
52,215 questions
59,993 answers
94,663 users