3
$\begingroup$

I'm trying to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ with $L^2 = \{w = w_1w_2 \mid w_1, w_2 \in L\}$ but I cant seem to find a proof that feels right.

I first tryed to show $L \in \mathsf{REG} \implies L^2 \in \mathsf{REG}$, by constructing an machine $M$ that consists of two machines $A=A'$ with $A$ recognizing $L$. $M$ has the same start states as $A$ but the final states of $A$ are put together with the starting states of $A'$. Further $M$ uses the same accepting states as $A'$. Hope that makes sens so far :D

Now to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ I'd argue the same way, but:

The machine $M'$ that accepts $L^2$ has to recognize $w_i \in L$ in some way, and because $L^2$ is regular, $M'$ has to be a NFA/DFA. So the machine has to check if $w_i \in L$ and this cant be done by using something else than a NFA/DFA.

This feels wrong and not very mathematical, so maybe somebody knows how to do this?

$\endgroup$

2 Answers 2

5
$\begingroup$

Your claim is false. Indeed, it is equivalent to prove that if a language $L$ is not regular, then also $L^2$ is not regular, but this is not true. Here Yuval Filmus gives (possibly) two examples of a non regular language whose "square" is regular, namely $L = \{ 1^p \mid p \text{ is an odd prime}\}$, under the Goldbach conjecture, and $L' = \{ 1^{a^2} \mid a \geq 0 \}^2=\{1^n \mid n \text{ is the sum of two squares}\}$.


For a simpler example, consider the set

$$\text{NP}=\{1^n\mid n \text{ is not prime}\}$$

Clearly NP is not regular (otherwise also its complementary would be regular), but NP$^2$ is regular, as its complementary is finite. Indeed, if $n$ is even and greater than or equal to 8, then $n=4+(n-4)$ and $4$ and $n-4$ are not prime and so $1^n\in \text{NP}^2$. Instead, if $n$ is odd and greater than or equal to 13, then $n=9+(n-9)$ and $9$ and $n-9$ are not prime, as $n-9$ is even and greater than 2, and again $1^n\in \text{NP}^2$ (actually, NP$^2=\{1^n\mid n\neq 3\}$, here I don't consider 1 as a prime number).


In general, if $L$ is a non regular language sufficiently "sparse", then there is a good chance that $(L^C)(L^C)$ is cofinite, and then regular. For example, again on a unary alphabet, one can consider the non regular language

$$\text{L}=\{1^n\mid n \text{ is not a power of }2\},$$

then it is easy to see that $L^2=\{1^n\mid n\not\in\{1,2 \}\}$, which is regular.

On a two letter alphabet one can consider the example below of Bernardo Subercaseaux (I think there's a little misunderstanding in his comment, as here we are considering the concatenation of a non regular language with itself), namely the language $L$ that is the complement of the language of well parenthesized strings on the alphabet $\{(,)\}$: in this case $L^2=\{(,)\}^*\setminus\{\varepsilon,(,)\}$, again regular.

Another simple example is given by the non regular language

$$\text{L}=\{w\in\{a,b\}^*\mid w \text{ is not of the form }a^nb^n\text{ with }n>0\},$$

then it is easy to see that $L^2=\{a,b\}^*$: indeed if $w\in L$, then $w=w\varepsilon\in L^2$, else if $w=a^nb^n$ then $w=a\cdot a^{n-1}b^n\in L^2$.

$\endgroup$
3
  • $\begingroup$ Well, should have searched better...sry for double asking, but thx for answering :) $\endgroup$
    – Algebruh
    Aug 24, 2020 at 22:53
  • 1
    $\begingroup$ Actually, it is an interesting and nontrivial question, and it gives me the opportunity to think to a simple example that I'll certainly use in class (I remebered Yuval's examples, but they are to complex for first year undergraduates). $\endgroup$
    – user6530
    Aug 24, 2020 at 23:01
  • 1
    $\begingroup$ Another example suitable for beginners is that over the alphabet $\{ (,)\}$ every string is the concatenation between a well parenthesized string and a non-well parenthesized string. The language of all strings is regular, while the other two are not, and usually undergraduates know that example. $\endgroup$ Aug 25, 2020 at 1:28
4
$\begingroup$

Here is a simple example. Take any non-regular language $N$ contained in $(aa)^+$ and consider the language $L = 1 + a(aa)^* + N$. Then $L$ is not regular since $L \cap (aa)^+ = N$ is not regular. On the other hand, $L^2 = a^*$ is regular.

$\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.