2
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Apr 19 '13 at 2:06

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\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 '13 at 23:36
  • 3
    $\begingroup$ No, I think it's perfect for cs.SE. $\endgroup$ – JeffE Apr 18 '13 at 21:16
5
$\begingroup$

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.)

$\endgroup$
  • 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$ – Huck Bennett Apr 17 '13 at 2:29
  • $\begingroup$ You're right. This argument actually applies to any kind of grammar. $\endgroup$ – Yuval Filmus Apr 17 '13 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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