# 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

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.

Using the fact that regular languages are closed under complement as in yuxiang's answer is the simplest approach, but here is a direct approach, in case anybody is interested.

First, we establish that for all $$m \geq 2$$, $$m!$$ is not a perfect square. I will not repeat a proof here, but you can see here for some justification.

Let $$L = \{1^m \mid m \text{ is not a perfect square}\}$$. Suppose $$L$$ is regular. Then, by the pumping lemma, we have a pumping length $$n$$. First, suppose $$n \geq 2$$. Then, by the above result, $$n!$$ is not a perfect square, and hence $$1^{n!} \in L$$. Since $$|1^{n!}| = n! \geq n$$, there exists a decomposition $$1^{n!} = uvw$$ where $$|uv| \leq n$$, $$|v| > 0$$, and $$uv^kw \in L$$ for $$k \geq 0$$. In particular, since $$0 < |v| \leq |uv| \leq n$$, we have that $$|v| \mid n!$$, and it follows that \begin{align*} uv^{n!(n! - 1)/|v| + 1}w & = uvwv^{n!(n! - 1)/|v|} && \text{since } u,v,w \in 1^* \\ & = 1^{n!}(1^{|v|})^{n!(n! - 1)/|v|} && \text{since } uvw = 1^{n!} \text{ and } v = 1^{|v|} \\ & = 1^{n!}1^{n!(n! - 1)} \\ & = 1^{(n!)^2} \notin L.\end{align*} However, the pumping lemma states that the left side of this chain of equalities is $$\in L$$, thus we have a contradiction.

To wrap things up, we should handle the case $$n \leq 1$$. In this case, we derive $$v = 1$$ (the terminal, not the number) from the inequality $$0 < |v| \leq |uv| \leq n \leq 1$$. Thus, we simply pump $$v$$ until $$|uv^kw|$$ is a perfect square, and we again have a contradiction.