Union of two (irregular) Context Free Language results a Regular Language?

Question

Given L1 and L2 (irregular) context free languages - Is it possible that L1 U L2 is regular?

I know that it is possible but I just cant find an example showing that. Would love to get some assistance.

Answer 1

Union of two CFLs can be regular?

Given L1 and L2 Context Free (but not regular) Languages, the is it possible that union of both L1 ∪ L2 is regular?

Yes Possible!

Suppose, first language L₁ is:

L₁ : { anbm | where n = m }

Language L₁ is a CFL but not a regular. Another way of writing L₁ language is anbn. I think this is one of the most conman example of CFL one can find in any text book of formal languages.

And Second language L₂ is:

L₂ : { anbm | where n ≠ m }

L₂ is again a CFL but not a regular. Basically L₂ is complement language of L₁.

Now, union of L₁ and L₂ is:

L : { anbm | there is no restriction over n and m values}

Language L = L1 ∪ L2 is a regular language and regular expression for L is a*b*.

So hint is union of complement CFLs are regular.

Note: Context-free languages are closed under union operation, so union of two CFLs are always CFL (that can be regular as class of regular languages is subset of class of CFLs), but it can't be a non-CFL e.g. CSL.

Adding on the basis of comments:

Intersection of two CFLs can be regular?

Given L1 and L2 Context Free (but not regular) Languages, the is it possible that intersection of both L1 ∩ L2 is regular?

Yes Possible!

Suppose, first language L₁ is:

L₁ : { anbm | where n = m }

And Second language L₂ is:

L₂ : { anbm | where n <= 3 or n ≠ m }

Language L = L1 ∩ L2 = {ab, aabb, aaabbb} is a finite set and hence also a regular set.