Are there two non-regular languages whose concatenation is regular?

Question

Here is my proof:

Consider non-regular languages $$L_1 = \{a^i b^j | i \neq j\} $$ and $$L_2 = \{b^n a^m | n \neq m\}$$ Then the concatenation of these two languages would be $$L_1 L_2 = \{a^i b^{j+n} a^m | i \neq j \land n \neq m\}$$

when $i = 0, m = 0$: $j + n \geq 2$

when $i = 0, m \neq 0$ : $j + n \geq 1$

when $i \neq 0, m = 0$: $j + n \geq 1$

when $i = 1, j + n \neq 1$: $m = 1$

otherwise: $j+n \geq 0$

Thus, the concatenation of $L_1$ and $L_2$ could be expressed as the union of five regular languages $A_1$ to $A_5$, each corresponding to one of the conditions above (Each of these languages could be proven to be regular by drawing a simple finite state automaton):

$$A_1 = \{b^n | n \geq 2\}$$ $$A_2 = \{b^n a^m | n \geq 1 \land m > 0\}$$ $$A_3 = \{a^n b^m | n > 0 \land m \geq 1\}$$ $$A_4 = \{a b^n a | n \neq 1\}$$ $$A_5 = \{a^i b^j a^k | j \geq 0\}$$ $$L_1 L_2 = A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5$$ Since the union of regular languages are closed, $L_1 L_2$ is regular.

If such a proof is correct, then two more questions arise: Are there countably infinite amount of such examples (which the concatenation pf two non-regular languages is a regular language)? Are there uncountably infinite amount of such examples?

Here is my proof for the first question:

Suppose there are five sets of languages $S_1$ to $S_5$:

$$S_1 = \{L | L = \{b^n | n > p\}, p \geq 2\}$$ $$S_2 = \{L | L = \{b^n a^m | n \geq p \land m > q\}, p \geq 1 \land q \geq 0\}$$ $$S_3 = \{L | L = \{a^n b^m | n > p \land m \geq q\}, p \geq 0, \land q \geq 1\}$$ $$S_4 = \{L | L = \{a b^n a | n \geq p\}, p \geq 1\}$$ $$S_5 = \{L | L = \{a^i b^j a^k | j \geq p\}, p \geq 0\}$$

It is obvious that $S_1$ to $S_5$ are all countably infinite. A particular set $S$ of such possible example exists $$S = \{ L | L = L_1 \cup L_2 \cup L_3 \cup L_4 \cup L_5, L_1 \in S_1 \land L_2 \in S_2 \land L_3 \in S_3 \land L_4 \in S_4 \land L_5 \in S_5 \}$$

The cardinality of set $S$ is the cross product of set $S_1$ to $S_5$. A finite cross product of countably infinite sets is countably infinite. Thus, there are countably infinite amount of such examples.

Accordingly, since we could set $p$ and $q$ of set $S_1$ to $S_5$ to be numbers in the natural numbers set, an infinite amount of countably infinite sets similar to $S_1$ through $S_5$ exists. The (infinite) cross product of all these (countably infinite) sets is uncountably infinite. Thus, there are uncountably infinite amount of such examples.

Are my proofs right? Is there easier way to prove these questions?

Answer 1

Take any nonregular language $L$. Denote by $L^c$ the complement of $L$ in $A^*$. Then the languages $1 + L$ and $1 + L^c$ are also nonregular. However, $A^* = L + L^c \subseteq (1 + L)(1 + L^c)$ and thus $(1 + L)(1 + L^c) = A^*$. This gives you uncountably many counterexamples, since there are only countably many regular languages and uncountably many subsets of $A^*$ if $A$ is nonempty.

Note: Here $+$ denotes union and $1$ denotes the language reduced to the empty word.

Answer 2

There are examples with $L_1 = L_2$. For example, take $L = \{ 1^p : p \text{ is an odd prime}\}$. If the Goldbach conjecture is true then $L^2 = (11)^+$ is regular, but $L$ isn't.

In order to get an unconditional example, consider the language $L = \{ 1^{a^2} : a \geq 0 \}$. It is easy to check that $L$ is not periodic – the distance between adjacent squares increases – and so $L$ is not regular. On the other hand, Lagrange's four square theorem shows that $L^4 = 1^*$. If $L^2$ is regular then $L^2$ is an example, and otherwise $L$ itself is an example. (In fact, $L^2$ is irregular, but this is a somewhat messy exercise.)