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

Question

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

Answer 1

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.