Let L1={a^nb^mc^(n+m) / n,m > 0} and L2={a^nb^nc^m / n,m > 0}.Is L3= L1 ∩ L2 context-free or not?

Question

Let L1={a^n b^m c^(n+m) / n,m > 0} and L2={a^n b^n c^m / n,m > 0}.Is L3= L1 ∩ L2 context-free or not?

My logic being is if n < m the intersection will yield a language (a^n b^n c^n) if n > m the intersection will yield a language (a^n b^m c^m) in both cases we have a CFG so is my interpretation correct?

Answer 1

I'm not sure if i understood your idea correctly, but if you try using the same n and m for both L1 and L2 and compute the intersection based on that, you are not right.

Besides that, the language {aⁿ bⁿ cⁿ | n > 0} is not CFG, as you can see as an example here https://en.wikipedia.org/wiki/Context-free_language or show by using the pumping lemma.

How can one see what L1 ∩ L2 looks like?
x ∈ L1 ∩ L2 <=> x ∈ L1 and x ∈ L2. So x must fullfill both restrictions of the two languages.
Therefore x ∈ L1 ∩ L2 is x = aⁿ b^m c^o where n = m because of L2 and o = n+m = n+n (n + m because of L1 and n + n because n = m).
This gives us L1 ∩ L2 = {aⁿ bⁿ c²ⁿ | n > 0}, which is not CFG.

Reason:

• Intuitively speaking a CFG can not count (more than once, aⁿ bⁿ is fine). But for achieving the pattern n, n, 2n, we have to count the amoung of a and b and then add the right amount of c.
• Pumping Lemma: We have to negate the original lemma in order to show that {aⁿ bⁿ c²ⁿ | n > 0} is not CFG. So we need to prove that for every p >= 0 there is a s ∈ {aⁿ bⁿ c²ⁿ | n > 0} which can NOT be split into uvwxy fullfilling |uvw| <= p and uv^kwx^ky ∈ {aⁿ bⁿ c²ⁿ | n > 0}.
  
  Proof: Given a p >= 0. We choose the word t = a^p b^p c^2p ∈ L1 ∩ L2. Now for every choose of uvwxy = t we can not pump uvwxy to still be ∈ L1 ∩ L2. This is because we only pump v and x. And |vwx| is <= p. So vwx can not contain a, b, and c but at max two of them. Now if we pump v and x we get more a than c, or the other way round and the result uv²wx²y is not in L1 ∩ L2.