Why did we choose n+1 in this proof of pumping lemma for context free language? I can't understand what are we trying to show by choosing i=n+1

shivajikobardan

Junior Member
Joined
Nov 1, 2021
Messages
107
Choosing i=n+1i = n+1 gets you a non-prime number n+n(j+k)=(n+1)(j+k)n+n*(j+k) = (n+1)(j+k). But this is the length of a "pumped" string, which, according to the lemma, must be in L3L_3 and thus have a prime length. The resulting contradiction proves that a set of all strings of prime length is not a context-free language.
 
Top