Proving that non-regular languages are closed under concatenation

Question

How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\{a^nb^n|n\ge1\}$ ?

Answer 1

You can't prove it because it isn't true: the class of non-regular languages isn't closed under concatenation.

Let $X\subseteq \mathbb{N}$ be any undecidable set containing $1$ and every even number. For example, take your favourite undecidable set $S$ and let $$X = \{0, 2, 4, \dots\} \cup \{1\} \cup \{2i+1\mid i\in S\}\,.$$ The language $\mathcal{L} = \{a^i\mid i\in X\}$ is undecidable, so it certainly isn't regular. But $$\mathcal{L}\cdot\mathcal{L} = \{a^{i+j}\mid i,j\in X\} = \{a^i\mid i\in\mathbb{N}\}\,,$$ is regular.

Answer 2

Here is another example showing that the claim is false. Let $L$ be any non-regular language over $\{0,1\}$, and take $$ L_0 = \{ 0 w : w \in L \} \cup \{ 1 w : w \in \{0,1\}^* \} \cup \{\epsilon\}, \\ L_1 = \{ 1 w : w \in L \} \cup \{ 0 w : w \in \{0,1\}^* \} \cup \{\epsilon\}. $$ You can check that $L_0,L_1$ are not regular, but $L_0L_1 = \{0,1\}^*$ is regular.

---

Another nice example uses Lagrange's four square theorem, which states that every non-negative integer is a sum of four squares. Define $L_1 = \{1^{n^2} : n \geq 0\}$, $L_2 = L_1^2$ and $L_4 = L_2^2$. The four square theorem shows that $L_4 = 1^*$ is regular. Conversely, the pumping lemma shows that $L_1$ is not regular. Hence either $L_2$ is regular, in which case $L_4 = L_2^2$ is a counterexample to the claim, or $L_2$ is not regular, in which case $L_2 = L_1^2$ is a counterexample to the claim. (In fact, $L_2$ is not regular.)

---

Yet another example assumes the Goldbach conjecture: every even integer larger than 4 is the sum of two odd primes. Let $L = \{ 1^p : \text{$p$ is an odd prime } \}$. Using the pumping lemma it is not hard to show that $L$ isn't regular. Assuming the Goldbach conjecture, $L^2 = \{ (11)^n : n \geq 3 \}$, which is regular.

Answer 3

Concatenation of two non-regular languages may be regular.

Constructive Proof:

Let $L$ be any non-regular language. Now, we know $L’$ is also non-regular.

Consider $(L \cup \{ \epsilon \})$ ; $(L’ \cup \{ \epsilon \})$, both of which are non-regular.

Now, $(L \cup \{ \epsilon \}).(L’ \cup \{ \epsilon \}) = \Sigma^*$, which is regular.

For concrete example:

Consider $L =$ Set of All Prime Numbers over $\{ 0 \}$ , 

$M =$ Set of All Composite Numbers over $\{ 0 \}$

Both $L,M$ are Non-regular.

Now, $L.M = \{ 0^n , n \geq 6 \}$ which is regular.