# concatenation of 2 non-context-free languages that is context-free but not regular

I'm having today a test on formal language theory, and I've seen a question about it I'm having hard time solving. The question is: Give an example of 2 languages, L,M which are non-context-free but LM(the concatenation) is a context-free language but not a regular language. Thanks in advance

Let $$1$$ denote the empty word. Let $$S = \{a^nb^n \mid n \geqslant 0\},\quad T= 1 + \{c^{2^n}\mid n \geqslant 0\},\quad L = ST,\quad M = 1 + (c^* - T).$$ Observe that $$c^* = T \cup M \subseteq (1+T)(1 + M) = TM$$ and hence $$TM = c^*$$. Now the languages $$L$$ and $$M$$ are not context-free but $$LM = Sc^*$$ is context-free but not regular.
• What is the meaning $1 + (c^* - T)$ and so on? Feb 11, 2020 at 18:09
• $+$ denotes union and $-$ set difference. Feb 11, 2020 at 18:16