5

I'm having some trouble understanding how to get the intersection of two context-free languages (L = L1 ∩ L2). I've seen the very common example where:

L1 = {a^i b^i c^j |  i,j ≥0}
L2 = {a^i b^j c^j |  i,j ≥0}
L1 ∩ L2 = {a^i b^i c^i  |  i ≥0}

but what about an example like this:

L1 = {a^i b^i c^j d^j |  i,j ≥0}
L2 = {a^j b^i c^i d^k |  i,j,k ≥0}
L1 ∩ L2 = ???

I get that I need to come up with context-free grammars for the both, which I have:

G1: S->AB
    A->aAb|λ
    B->cBd|λ

G2: S->aS|AB
    A->bAc|λ
    B->dB|λ

But at this point, I don't know how to intersect the two and come up with a language. I was wondering if someone could show me how. Thank you in advance.

user2256498
  • 85
  • 1
  • 8

1 Answers1

4

From the first language, you need the same number of as and bs. From the second language, you need the same number of b and cs and again from the first language you need the same number of cs and ds - so all the words that have the same number of as,bs,cs, and ds.

So basically {a^i b^i c^i d^i | i is a natural number}

Note - is the result a context free language? Why? ;)

Benjamin Gruenbaum
  • 270,886
  • 87
  • 504
  • 504
  • If you want a more formal proof (the text above _is_ a proof in case there was a doubt) - I don't mind providing one, but that might be much more abstract. If you formalize the language as an intersection of the requirements on it (and do justify the construction) you might be able to see it more clearly. – Benjamin Gruenbaum Mar 03 '14 at 23:23