Prove that the language L ap p prime is not contextfree Yo

Prove that the language L = {a^p | p prime} is not context-free. You may assume the mathematical result (known since antiquity) that the number of prime numbers is infinite.

Solution

We can solve this by contradiction using Pumping Lemma. Let\'s assume that \'L\' is context free.

Let v=a^q and y=a^t , noting the pumping lemma requires q+t>0. Let r=|uxz|=pqtr=|uxz|=pqt.

Then

|uv^ray^rz|= r+rq+rt=r(1+q+t),

is divisible by both r and 1+q+t>1 and thus is not prime as long as r>1.

Then there are two unsettled cases: if r=0

|uv^2xy^2z|=|v^2y^2|=2p,

is not prime. Finally, if r=1,

|uv^p+1xy^p+pz|=1+(p+1)q+(p+1)t=1+(p+1)(q+t)=1+(p+1)(p1)=p^2

is not prime.