Editing Chomsky normal form (section)

==Alternative definition==

=== Chomsky reduced form ===
Another way<ref name="Hopcroft.Ullman.1979"/>{{rp|92}}<ref>Hopcroft et al. (2006){{page needed|date=November 2014}}</ref> to define the Chomsky normal form is:

A [[formal grammar]] is in '''Chomsky reduced form''' if all of its production rules are of the form:
: <math>A \rightarrow\, BC</math> or
: <math>A \rightarrow\, a</math>,
where <math>A</math>, <math>B</math> and <math>C</math> are nonterminal symbols, and <math>a</math> is a [[terminal symbol]].  When using this definition, <math>B</math> or <math>C</math> may be the start symbol.  Only those context-free grammars which do not generate the [[empty string]] can be transformed into Chomsky reduced form.

=== Floyd normal form ===
In a letter where he proposed a term [[Backus–Naur form]] (BNF), [[Donald E. Knuth]] implied a BNF "syntax in which all definitions have such a form may be said to be in 'Floyd Normal Form'",
: <math>\langle A \rangle ::= \, \langle B \rangle \mid \langle C \rangle</math> or
: <math>\langle A \rangle ::= \, \langle B \rangle \langle C \rangle</math> or
: <math>\langle A \rangle ::=\, a</math>,
where <math>\langle A \rangle</math>, <math>\langle B \rangle</math> and <math>\langle C \rangle</math> are nonterminal symbols, and <math>a</math> is a terminal symbol,
because [[Robert W. Floyd]] found any BNF syntax can be converted to the above one in 1961.<ref>{{cite journal | url=https://core.ac.uk/download/pdf/82003923.pdf |archive-url=https://web.archive.org/web/20210305050258/https://core.ac.uk/download/pdf/82003923.pdf |archive-date=2021-03-05 |url-status=live | author=Floyd, Robert W. | title=Note on mathematical induction in phrase structure grammars. | journal=Information and Control | volume=4 | pages=353&ndash;358 | year=1961 | issue=4 | doi=10.1016/S0019-9958(61)80052-1 | doi-access=free }} Here: p.354</ref>  But he withdrew this term, "since doubtless many people have independently used this simple fact in their own work, and the point is only incidental to the main considerations of Floyd's note."<ref name="knuth1964">{{cite journal |last=Knuth |first=Donald E. |date=December 1964 |title=Backus Normal Form vs. Backus Naur Form |journal=Communications of the ACM |doi=10.1145/355588.365140 |volume=7 |issue=12 |pages=735–736|s2cid=47537431 |doi-access=free }}</ref> While Floyd's note cites Chomsky's original 1959 article, Knuth's letter does not.