Show that L ak k is a square is not regularSolutionLet p b

Show that L = {a^k | k is a square} is not regular.

Solution

Let p be the pumping length for the language. Let s = a^(p^2), according to pumping lemma s can be divided in to three parts xyz such that

1) |xy|<=P

2) |y| > 0

3) xy^iz belongs to L.

As |xy|<=p which implies |y|<=p lets assumes y = a^j where j<=p, lets consider xy^2z which will be a^(p2+j).

p^2 + j <= p^2 + p < p^2 + 2p + 1 < (p+1)^2. Hence xy^2z does not belong to L. Therefore it is not a regular language.