Skip to content

Chomsky Normal Form

Restrict a context-free grammar to binary nonterminal or single-terminal productions, with only a bounded start-symbol exception for the empty word.

Version
v1 · 2026-10-03 · History
Domain-specific #
13056
Aliases
CNF, Chomsky Normal Form Grammar

Core Idea

Chomsky normal form (CNF) is a restricted form of context-free grammar. Its ordinary rules are A → B C for two nonterminals or A → a for one terminal. Under the stated convention, S → ε is allowed only when the language contains the empty word and the start symbol never appears on a right-hand side. The form belongs to the grammar's current rule inventory; conversion and parsing are separate procedures.[^ref-a9c1e7146fc1]

Scope of Application

Formal-language theory uses CNF to standardize derivations while retaining the generated set of strings. In language parsing, binary phrase rules and lexical emissions support a chart parser; a probabilistic CFG can also be written in CNF. Ordinary CFG conversion establishes language equivalence, not automatically identical parse trees or probability distributions.[ref-a9c1e7146fc1][ref-206467e5003a]

Clarity

A language itself is not “in CNF”: one grammar for it may pass the rule test while another does not. A remaining A → B C D or A → B rule disqualifies that grammar even though it is context-free. The bounded start-rule exception does not authorize arbitrary empty productions.[^ref-a9c1e7146fc1]

Manages Complexity

Binary rules let a parser combine two spans at each internal step, and lexical rules ground spans in terminals. This regularity helps dynamic programming, but a particular runtime bound depends on the grammar and algorithm. Binarization may also introduce helper symbols that should be traced back to original rules when explaining a parse.[ref-ae5221665a82][ref-206467e5003a]

Abstract Reasoning

Separate the form-membership test, a language-preserving normalization theorem, and a parser that exploits the result. The first is checked by inspecting rules, the second constructs an equivalent grammar, and the third is optional. Live Context-Free Grammar is the proposed strict genus; Chomsky Hierarchy and Kuroda Normal Form are different neighbors.[^ref-a9c1e7146fc1]

Knowledge Transfer

A grammar for formal marker strings and a weighted phrase-structure grammar use unlike symbols, but both can have exactly the binary and lexical production shapes. That is genuine transfer of a grammar test, not a general claim that any binary tree is CNF.[ref-a9c1e7146fc1][ref-206467e5003a]

[^ref-a9c1e7146fc1]: Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Languages, Automata and Grammars, University of Pennsylvania CIS5110 notes (18 March 2026), §7.3, PDF pp. 213–220. [^ref-ae5221665a82]: Cornell CS6741, "Parsing" lecture notes (2015), PDF pp. 33–53. [^ref-206467e5003a]: MIT OpenCourseWare 6.864, "Advanced Natural Language Processing," Lecture 4 (2005), PDF p. 18.

Relationships to Other Abstractions

Local relationship map for Chomsky Normal FormParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Chomsky Normal FormDOMAINDomain-specific abstraction: Context-Free Grammar — is a kind ofContext-FreeGrammarDOMAIN

Current abstraction Chomsky Normal Form Domain-specific

Parents (1) — more general patterns this builds on

  • Chomsky Normal Form is a kind of Context-Free Grammar Domain-specific

    Every CNF grammar is a CFG with additional production-shape restrictions.

Hierarchy paths (2) — routes to 2 parentless roots

Neighborhood in Abstraction Space

Chomsky Normal Form sits in a moderately populated region (50th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Formal Grammar & Syntactic Structure (16 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08