I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable.

I could not, however, find a citation for this quotation (and searching has failed to turn up a restatement of this result somewhere else).

Can anyone provide a proof or a citation to the original proof for this result? Can anyone state that it is false?

  • $\begingroup$ It never fails that I find the result moments after posting ... The quotation with a citation is "To show this result, we rely on the well-known representation of recursively enumerable languages as the homomorphic image of the intersection of two context-free languages (Ginsburg et al., 1967)." but perhaps someone would like to go ahead and lay it out in an answer (I don't have that reference at hand) $\endgroup$
    – Stephen
    Apr 16, 2013 at 23:36
  • 3
    $\begingroup$ No, I think it's perfect for cs.SE. $\endgroup$
    – JeffE
    Apr 18, 2013 at 21:16

1 Answer 1


This result more easily follows from the fact that every context-free grammar is recursively enumerable, by enumerating all parse trees. The intersection of any two r.e. languages is r.e. - just enumerate them both and output every word that appears on both lists. The other direction (given by the quotation you found) is more interesting.

Edit: As Huck correctly comments, there are actually efficient algorithms for deciding membership in context-free languages. But the argument above holds for the most general grammars possible, in which case we prove that the language corresponding to any grammar is recursively enumerable. (Replace parse trees with the a sequence of rule applications.)

  • 5
    $\begingroup$ Errr... deciding membership in the intersection of two CFLs is in P. Just decide whether a string is in each language independently, which is doable in polynomial time (e.g. via converting to Chomsky normal form, and applying CKY parsing). $\endgroup$ Apr 17, 2013 at 2:29
  • $\begingroup$ You're right. This argument actually applies to any kind of grammar. $\endgroup$ Apr 17, 2013 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.