I believe that most "natural" ways of transforming a grammar to the GNF should preserve the number of parse trees for each string. For example, Urbanek's construction from the paper "On Greibach normal form construction" seems to do the job.

What I need is the statement that for every context-free grammar there exists a grammar in GNF that every word has the same number of parse trees for both grammars (therefore this grammars define the same language; but it should be noted that the equality of the number of the parse trees is stronger condition).

Unfortunately, proving this rigorously looks really tedious and probably won't add any conceptual value to the paper I currently participate in writing. Moreover, this result can't possibly be original and therefore it is much better to cite it rather than to reprove it again. However, all my attempts to find a paper where this result is stated directly were futile.

Some requirements (all not strict, though):

  1. For simplicity of quoting, I would prefer a paper where this result is stated as a theorem, lemma, corollary or something "noticeable" like this, preferably not as a remark in the middle of the proof (though the latter also would be okay for the lack of the former).
  2. Situations, where this result is not stated at all and just immediately follows from some deeper theory (but the fact that it follows is not established in the paper) are less preferable, of course, but still fine, as long as the main results of the theory are easy to state.
  3. In the same vein, if the result is proved for weighted grammars (with the number of parse trees being replaced with weigt of the word), it is completely fine.

While not probable, it still may happen that this result is incorrect. In this case, link to the disproof or a disproof as the answer would be nice.

UPD It seems that lemma 4 in this paper does the job. However, if someone finds a link that does not mention multigrammar, I would still appreciate that.


Your Answer

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

Browse other questions tagged or ask your own question.