go-v.orgcodex
Menu
Page tools

codex · Philosophy

Chomsky normal form

In formal language theory, a context-free grammar, G, is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form:

A → BC, or A → a, or S → ε, where A, B, and C are nonterminal symbols, 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, and the third production rule can only appear if ε is in L(G), the language produced by the context-free grammar G. Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form and has a size no larger than the square of the original grammar's size.

Wikipedia contributors, "Chomsky normal form", Wikipedia, revision 1337949563, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex