[Solved]: Proving that non-regular languages are closed under concatenation

Problem Detail: 

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

Asked By : TT8

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41862