2
$\begingroup$

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

$\endgroup$

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.