# Finding string in Pumping Lemma

I'm trying to prove that the Language $L_1$ = $\{1^m :$ m is not a perfect square$\}$ is not regular. I proved before that L = $\{1^m :$ m is a perfect square$\}$ is not regular, I thought that I could proof $L_1$ in a similar way but I'm stuck right now, I tried several estimations but nothing seems to work. What I got so far:

Assume L is regular, that is there exists an $n \in \mathbb{N}$ such that every $x \in L$ with $|x| \geq n$ can be decomposed such that the three conditions of the Pumping Lemma hold. Let x = $1^{n^2 +1}$ then clearly $|x| \geq n$, now $uv^0w$ should also be an element of the language but $uw = 1^{n^2 +1-|v|}$... So how can I argue now that uw is a square? A little hint would be awesome

Thanks

• $uw$ need not be a square. Although the pumping lemma gives a lot more information than you used ($uv^kw$ has to be a non-square for all $k$), I don't see that pumping is a good way to approach this problem. If you know the theorem that the complement of a regular language is regular, then you're done, since you already showed that the set of square-length strings of $1$'s is not regular. If you don't know that theorem, try to prove it as an exercise. – Andreas Blass Oct 16 '17 at 21:18

As you have already proved that $\overline{L_1}$ (the complement of $L_1$) is not regular, you can base your argument on that to prove $L_1$ is not regular according to closure properties.