Show that the language {a^n^2/n>=1} is not context free

# Show that language is not context free

Let us assume that the language L is context free, so the Pumping Lemma applies, meaning that there is an integer p>1 such that we can write the string ap2 as the concatenation of strings uvxyz with |vy|>0 and |vxy|=t≤p.

Hence, we’ll have

0<|vy|=t≤p

This means that when we pump uvxyz to uvixyiz we’ll have

p2<|uvixyiz|=p2+(i−1)t≤p2+(i−1)p

Choosing i=2 gives us

p2<|uv2xy2z|≤p2+p

Now, in length order, the next string in L after ap2 will be a(p+1)2. Here’s the hint: use this fact to show that uvixyiz can’t possibly be in L, contradicting the Pumping Lemma consequence that all the pumped strings are in L, so consequently L cannot be a CFL

reference: cs.stackexchange.com

**satish**#3

As we know that every regular language is context free language .To show the language is context free ,it is enough to show that it is not regular.but vice-versa is not possible.to show the language is non regular we goes to pumping lemma.so

Z=a^(n^2+1)

According to pumping lemma |z|>=n here n is pumping lemma constant.so we divide z=I’ve such that |v|>0,|uv|<n and for each i u(v^i)w belongs to L

As from these three rules we divide three rules we divide z into three parts .for example u=a,v=aaaa…(n-1 times),w=aaa…(n^2-n times)…

For i=2 |u(v^2)w| is greater than n^2 .so u(v^2)w doesn’t belongs to L .so given language is non regular .so it is not context free