Problem Detail: How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L={a^nb^n|nge1}$ ?
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 $Xsubseteq 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+1mid iin S},.$$ The language $mathcal{L} = {a^imid iin X}$ is undecidable, so it certainly isn’t regular. But $$mathcal{L}cdotmathcal{L} = {a^{i+j}mid i,jin X} = {a^imid iinmathbb{N}},,$$ is regular.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41862