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
Best Answer
An important property of regular languages is that the latter are closed under complementation.
In other words, the complement of a regular language is also regular.
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.