Show that language is not context free


#1

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


#2

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


#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