Proving $L=\{0^n \mid \text{n is a perfect square}\}$ is not a Regular Language without the Pumping Lemma

2.3k Views Asked by At

Is this a valid way of going about proving the proposition?

Let $L = \{0^n \mid \text{n is a perfect square}\}$. The regular languages are closed under concatenation. So if $x \in L, y \in L$, then $xy \in L$. So take $0, 0000 \in L$. $00000 \notin L$. Therefore, $L$ is not closed under concatenation, so it is not regular.

2

There are 2 best solutions below

0
On BEST ANSWER

You’ve misunderstood closure under concatenation. The class of regular languages is closed under concatenation; individual regular languages in general aren’t. Thus, if the language $L$ is regular, so is the language $L\circ L$, but that does not mean that $0000\in L$ because $00\in L$.

0
On

No, it is not.

The statement "The regular languages are closed under concatenation" means the following

If $L_1$ and $L_2$ are regular, then $L = \{xy \ | \ x \in L_1, y \in L_2\}$ is regular.

Your interpretation of the statement seems to be

If $L_1$ is regular and $x,y \in L_1$, then $xy \in L_1$

which is not true in general (just take any finite regular language*).


* - Well, exceptions here being the empty language and the language containing only the empty string