[Solved]: Is the intersection of two context free languages recursively enumerable?

Problem Detail: 

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?

Asked By : Stephen

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11393