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

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.