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
94

blamocur

Senior Member
Joined
Oct 30, 2021
Messages
1,209
Choosing [imath]i = n+1[/imath] gets you a non-prime number [imath]n+n*(j+k) = (n+1)(j+k)[/imath]. But this is the length of a "pumped" string, which, according to the lemma, must be in [imath]L_3[/imath] 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