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

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?

• For the initial example: In the second case you want $j+n\ge 1$, not $j+b\le 1$, and the fourth case should read ‘when $i=1,m=1:j+n\ne 1$’. $A_4$ should be $\{ab^na:n\ne 1\}$, and $A_5$ should be $\{a^ib^ja^k:i,k\ge 1,j\ge 0,\langle i,k\rangle\ne\langle 1,1\rangle\}$. Actually, you could combine $A_4$ and $A_5$ into $\{a^ib^ja^k:i,k\ge 1,j\ge 0,\langle i,j,k\rangle\ne\langle 1,1,1\rangle\}$. Mar 18, 2015 at 3:22
• I have edited according to your corrections. What about the rest of the prove? Is it correct? Mar 18, 2015 at 3:43

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.

• Excellent example! Mar 19, 2015 at 19:15
• @yuval-filmus You are welcome. Mar 20, 2015 at 13:10

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.)

• Could you please tell me how $(1^p)^*$ is equivalent to $1^*$ where p is prime number. As I can see "1" itself cant be generated. How is this true? Aug 9, 2016 at 14:47
• Fortunately, I'm never claiming that. Aug 9, 2016 at 14:50
• Sorry!! I have read it at many places..just saw your concatenation example and that thought came. so asked its validity. Aug 9, 2016 at 14:53
• If the comment is not about my post, it shouldn't be a comment to my post. Aug 9, 2016 at 14:54
• no i never meant that Aug 9, 2016 at 14:58