4

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.

Njol
  • 3,271
  • 17
  • 32
Rouki
  • 2,239
  • 1
  • 24
  • 41

1 Answers1

7

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.

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • Btw, what about intersection? – Rouki Jan 19 '14 at 11:30
  • 1
    @Rouki Intersection always impose more restriction over the rules of language regeneration so intersection of two CFLs may not be even CFL. Remember regular is less restricted language and restriction increases as from rl -> cfl -> csl. – Grijesh Chauhan Jan 19 '14 at 11:33
  • So, is that impossible to find an example of 2 CFLs that their intersection is regular language? – Rouki Jan 19 '14 at 11:54
  • 1
    @Rouki Yes possible! Suppose **L1**: `{a^nb^m where (n < 3 or m != n)}` is a CFL (but not regular) and **L2**: `{a^nb^m where (n == m)}` is CFL (not regular) NOW, **`L1 ∩ L2`** = `{ab, aabb, aaabbb}` that is [a finite set hence Regular too](http://stackoverflow.com/a/20818068/1673391). `¯\_(ツ)_/¯` – Grijesh Chauhan Jan 19 '14 at 12:15
  • @Rouki read updated answer, l1 and l2 are not complement languages. – Grijesh Chauhan Jan 20 '14 at 04:58
  • Sorry shouldn't CFL be less restricted than RL, because PDA is more powerful than (N/D)FA? – Sibbs Gambling Oct 04 '16 at 21:49
  • @GrijeshChauhan , i can use your first example to prove that it is possible that L1 intersection L2 can be regular , given L1,L2=some CFL but not regular. L1={a^n b^m |n=m} and L2={a^n b^m |n!=m} .L1 intersection L2 =phi. which is regular.right? – laura Sep 21 '17 at 15:38