1
$\begingroup$

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?

I cannot find an reference.

$\endgroup$
  • 6
    $\begingroup$ Look at Definition 8 and Theorem 5 in Chomsky's On Certain Formal Properties of Grammars, Information and Control 2(2): 137­--167, 1959 (dx.doi.org/10.1016/S0019-9958%2859%2990362-6). $\endgroup$ – Sylvain May 11 '14 at 21:18
  • $\begingroup$ @sylvain Why don't you turn your comment into an answer? On page 150 of this article, Chomsky states: "Theorem 5 asserts in particular that all type 2 languages can be generated by grammars which yield only trees with no more than two branches from each node. That is, from the point of view of generative power, we do not restrict grammars by requiring that each phrase have at most two immediate constituents". $\endgroup$ – J.-E. Pin May 29 '14 at 15:34

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.