Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 358
Rouki Avatar asked Mar 21 '23 21:03

Rouki


1 Answers

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 L1 is:

L1 : { anbm | where n = m }

Language L1 is a CFL but not a regular. Another way of writing L1 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 L2 is:

L2 : { anbm | where n ≠ m }

L2 is again a CFL but not a regular. Basically L2 is complement language of L1.

Now, union of L1 and L2 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 L1 is:

L1 : { anbm | where n = m }

And Second language L2 is:

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

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

like image 122
Grijesh Chauhan Avatar answered May 16 '23 06:05

Grijesh Chauhan