1
$\begingroup$

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

$\endgroup$
  • $\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
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.