Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Chomsky normal form
open-in-new
<p>In <a href="/facts/Formal_language/crDTyP8q">formal language</a> theory, a <a href="/facts/Context-free_grammar/yu1FFdK4">context-free grammar</a>, <i>G</i>, is said to be in Chomsky normal form (first described by <a href="/facts/Noam_Chomsky/3rtpzlER">Noam Chomsky</a>) if all of its <a href="/facts/Production_(computer_science)/J7E2FXKs">production rules</a> are of the form: </p> <i>A</i> → <i>BC</i>, or <i>A</i> → <i>a</i>, or <i>S</i> → ε, <p>where <i>A</i>, <i>B</i>, and <i>C</i> are <a href="/facts/Nonterminal_symbol/3BLz2wJU">nonterminal symbols</a>, the letter <i>a</i> is a <a href="/facts/Terminal_symbol/3BLz2wJU">terminal symbol</a> (a symbol that represents a constant value), <i>S</i> is the start symbol, and ε denotes the <a href="/facts/Empty_string/T7udJlmQ">empty string</a>. Also, neither <i>B</i> nor <i>C</i> may be the <a href="/facts/Start_symbol_(formal_languages)/QLxaQNAz">start symbol</a>, and the third production rule can only appear if ε is in <i>L</i>(<i>G</i>), the language produced by the context-free grammar <i>G</i>.: 92–93, 106 </p><p>Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an <a href="/facts/Equivalence_(formal_languages)/NVzANpS6">equivalent</a> one which is in Chomsky normal form and has a size no larger than the square of the original grammar's size. </p>