Concatenation of context-free-language and non-context-free language

computer sciencecontext-free-grammarformal-languagesregular-language

CFL = context-free-language

I would like to know does the concatenation of one CFL and one non-CFL does it necessarily give a non-CFL.

I am trying to solve the following: enter image description here

I know that CFLs are closed under concatenation.

And my approach to solve the problem is to let

L = L1.L2 where L1 = a, since L is CFL and L1 is also CFL then L2 must be CFL, however I am not sure if my approach is right!

Best Answer

The concatenation of $A^*$ with any language $L$ containing the empty word is equal to $A^*$. In particular, you can take for $L$ a non context-free language or even a non-recursive one.

Now, for your other question, $f(L) = a^{-1}L$, the left quotient of $L$ by $a$. Now, context-free languages are closed under left quotient by a regular language.

Related Question