Editing Chomsky normal form (section)

{{Short description|Notation for context-free formal grammars}}
{{distinguish|conjunctive normal form}}
In [[formal language]] theory, a [[context-free grammar]], ''G'', is said to be in '''Chomsky normal form''' (first described by [[Noam Chomsky]])<ref>{{cite journal |last=Chomsky |first=Noam |date=1959 |title=On Certain Formal Properties of Grammars |journal=Information and Control |volume=2 |issue=2 |pages=137–167 |doi=10.1016/S0019-9958(59)90362-6 |doi-access= }} Here: Sect.6, p.152ff.</ref> if all of its [[production (computer science)|production rules]] are of the form:<ref>{{cite web |last1=D'Antoni |first1=Loris |title=Page 7, Lecture 9: Bottom-up Parsing Algorithms |url=http://pages.cs.wisc.edu/~loris/cs536/slides/lec9.pdf |archive-url=https://web.archive.org/web/20210719220611/http://pages.cs.wisc.edu/~loris/cs536/slides/lec9.pdf |archive-date=2021-07-19 |url-status=live |website=CS536-S21 Intro to Programming Languages and Compilers |publisher=University of Wisconsin-Madison}}</ref><ref>{{Cite book |last=Sipser |first=Michael |url=https://archive.org/details/introductiontoth00sips |title=Introduction to the theory of computation |date=2006 |publisher=Thomson Course Technology |isbn=0-534-95097-3 |edition=2nd |location=Boston |at=Definition 2.8 |oclc=58544333 |url-access=registration}}</ref>
: ''A'' → ''BC'', &nbsp; or
: ''A'' → ''a'', &nbsp; or
: ''S'' → ε,
where ''A'', ''B'', and ''C'' are [[nonterminal symbol]]s, the letter ''a'' is a [[terminal symbol]] (a symbol that represents a constant value), ''S'' is the start symbol, and ε denotes the [[empty string]].  Also, neither ''B'' nor ''C'' may be the [[Start symbol (formal languages)|start symbol]], and the third production rule can only appear if ε is in ''L''(''G''), the language produced by the context-free grammar ''G''.<ref name="Hopcroft.Ullman.1979">{{cite book |last1=Hopcroft |first1=John E. |last2=Ullman |first2=Jeffrey D. |date=1979 |title=Introduction to Automata Theory, Languages and Computation |publisher=Addison-Wesley Publishing |location=Reading, Massachusetts |isbn=978-0-201-02988-8 |url=https://archive.org/details/introductiontoau00hopc }}</ref>{{rp|92–93,106}}

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an [[Equivalence (formal languages)|equivalent]] one<ref group=note>that is, one that produces the same [[Context free grammar#Context-free language|language]]</ref> which is in Chomsky normal form and has a size no larger than the square of the original grammar's size.