concatenation & union - regular and context free languages

Question

Given L1 context free non regular language. Given L2 regular language.

Is it possible that L1 U L2 = regular language ? Also, is it possible that L1*L2 = regular language ?

I think that the 2nd one is impossible. But I'm not sure.

Would love to see an example if one of the abovementioned statements (or both) is/are true.

Answer 1

Is it possible that L1 U L2 = regular language ?

Yes, Possible.

A simple case is: if L₁ is sub-set of L₂ then L1 U L2 will be regular (=L2), for example: L₁ : { anbn | where n >= 0 } and L2 = (a + b)*

is it possible that L1 * L2 = regular language ?

No, Concatenation of a context-free and Regular will be context-free (because constraint in pattern of L1 is still there in L1 * L2).

_{Adding a reference: CS 273: Closure Properties for Context-Free Languages}

Answer 2

yes, Concatenation of a context-free and Regular will be regular

take L1= a^nb^n which is CFL and take L2 = Ø which is regular.

so L1.L2 = (a^nb^n).Ø = Ø which is regular

Note: For concatenation of two language must be regular , there has to be atleast one language to be regular.

Answer 3

Is it possible that L1 U L2 = regular language ?

Yes, it is possible. But its always better to take an example:

L1 = {0*1*} (regular) and L2 = {0^n1^n |n>=0} (context-free).

L = L1 U L2 = {0*1*} which is regular language but since every regular language is context-free. So, we can say the union of two always results in context-free language.

Is it possible that L1·L2 = regular language ?

the concatenation of a regular and a context-free language always results in a context-free language.Take the above example again:

L = L1·L2 = {(0*1*)·(0^n1^n) |n>=0} (context free).

It can be regular too if for example one of L1 or L2 is Ø, L1·L2 will result in Ø (regular). But since, all regular languages are context-free, Ø is also a context-free.

Check this out: Geeks for Geeks