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

regular-language formal-languages context-free-language
Rouki picture Rouki · Jan 19, 2014 · Viewed 7.3k times · Source

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

Grijesh Chauhan picture Grijesh Chauhan · Jan 19, 2014

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.

Related questions

Context-free grammar for the language L = {a^(n)b^(m)c^(k): m = |i - k|}

I have this language L = {a^n b^m c^k: m = |n - k|}. I know m = |n - k| can be expressed in two ways 1) m = n - k for n >= k or n = m + k 2) m = …

Read More
Left-Linear and Right-Linear Grammars

I need help with constructing a left-linear and right-linear grammar for the languages below? a) (0+1)*00(0+1)* b) 0*(1(0+1))* c) (((01+10)*11)*00)* For a) I have the following: Left-linear S --> B00 | S11 B --> B0|B1|011 Right-linear S --> 00B | 11S …

Read More
What is a regular language?

I'm trying to understand the concept of languages levels (regular, context free, context sensitive, etc.). I can look this up easily, but all explanations I find are a load of symbols and talk about sets. I have two questions: Can …

Read More