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


  • $\begingroup$ $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. $\endgroup$ – Andreas Blass Oct 16 '17 at 21:18

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.