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

<p>I cannot find an reference.</p>

CC BY-SA 3.0
2014-05-11T21:18:41.987Z
Look at Definition 8 and Theorem 5 in Chomsky's *On Certain Formal Properties of Grammars*, Information and Control 2(2): 137­--167, 1959 (http://dx.doi.org/10.1016/S0019-9958%2859%2990362-6).
Sylvain
CC BY-SA 3.0
2014-05-29T15:34:57.907Z
@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".
J.-E. Pin
<fl.formal-languages><automata-theory><context-free>
Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?
S0rin
# Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?

(Asked by: username_0 on 2014-05-11)

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

I cannot find an reference.

**Tags:** fl.formal-languages, automata-theory, context-free
> **Comments:**
> **username_1**: Look at Definition 8 and Theorem 5 in Chomsky's *On Certain Formal Properties of Grammars*, Information and Control 2(2): 137­--167, 1959 (http://dx.doi.org/10.1016/S0019-9958%2859%2990362-6).  
> **username_2**: @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".  

---

## 0 answers

