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
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Formal Language Theory → Computer Science & Software Engineering
Aliases: CNF, Chomsky Normal Form Grammar

Core Idea¶

Chomsky normal form (CNF) is a shape restriction on a context-free grammar (CFG), not a different language family or a parser. Each ordinary production is either A → B C, with exactly two nonterminals, or A → a, with exactly one terminal. Under the convention used here, S → ε is the only exceptional empty production: it is available if the language includes the empty word, and S does not occur on any production right-hand side. A grammar passes the CNF test by inspecting its productions, whether or not anybody converted or parsed it.^[1]

The theorem that any context-free language has an equivalent CNF grammar concerns language preservation: the original and converted grammars generate the same set of strings. It does not claim identical derivation trees or, for weighted grammars, automatically preserved parse probabilities. The conversion is a way to obtain the form; its particular algorithm is not a constitutive part of a grammar already in it.^[1]^[2]

Structural Signature¶

Sig role-phrases: CFG carrier → binary nonterminal rules → single-terminal rules → bounded start-symbol empty exception.

Context-free production system. The carrier is a grammar with nonterminals, terminals, productions and a start symbol. Without that carrier, there is no CNF classification.^[1]
Binary nonterminal branch. Every ordinary nonlexical rule has exactly two nonterminals on its right: A → B C. A remaining unary A → B or long A → B C D rule fails this test.^[1]
Single-terminal emission. Every ordinary terminal-producing rule is A → a. A terminal mixed with nonterminals on one right side is outside the form.^[1]
Bounded empty-string exception. If ε is generated, the specified convention permits S → ε only with S absent from right sides. This is an exceptional rule, not permission for arbitrary nullable nonterminals.^[1]

Rule weights, helper-symbol names, normalization history and a parser execution are not additional necessary roles.

What It Is Not¶

CNF is not every CFG. A grammar remains context-free when A → B C D appears, but that particular grammar is not in CNF until the long rule is replaced by allowed rules. It is not the Chomsky hierarchy, which compares the expressive reach of grammar classes, nor Kuroda normal form, which regulates a different kind of grammar and permits different production forms. The live CFG node is the strict genus; these other two are related by formal-language topic, not interchangeable identities.^[1]

Nor is CNF the Cocke–Younger–Kasami algorithm. Binary rules make certain chart recurrences convenient, but the form exists before a parser is selected. An ordinary conversion theorem concerns string-language equivalence; it should not be casually extended to equality of probability distributions for a probabilistic CFG.^[1]^[2]

Scope of Application¶

In formal-language proofs, a grammar can be normalized to reason about derivation-tree branching while retaining the generated language. Gallier and Quaintance give the precise rule shapes, the restricted empty exception and a construction showing the existence of equivalent CNF grammars. The theorem does not mean the normalized grammar preserves the original productions or every parse-tree distinction.^[1]

In natural-language parsing, phrase categories can be binarized into constituents that combine two at a time, with lexical rules emitting words. Cornell works through phrase-structure conversion; MIT presents a probabilistic grammar already written in the binary/lexical shape for a chart-parsing calculation. We do not infer from those notes that a naive CFG conversion preserves all PCFG probabilities.^[3]^[2]

Some references define CNF only for languages excluding ε and handle the empty word outside the normal form. This entry uses the explicitly stated start-rule convention, so a claimed counterexample must be evaluated under the same convention.^[1]

Clarity¶

The question “Is the language in CNF?” is malformed: CNF names a grammar form. A context-free language may be generated by one grammar in CNF and another not in CNF. If a rule A → a B remains, it is not saved by the fact that the language is context-free; the terminal must be separated and the production binarized or otherwise replaced.^[1]

Likewise, the start-symbol exception is not a blanket allowance for empty productions. State whether the language includes ε and whether S appears on any right side. Those two checks determine whether S → ε is permitted under this convention.^[1]

Manages Complexity¶

The rule discipline compresses parser case analysis: an internal parse-chart item can be built from two spans and a binary production, while a lexical item comes from one terminal. This regularity supports dynamic programming, but the source's cubic-style bound depends on grammar size, sentence length and algorithmic assumptions; CNF does not itself run in a time bound.^[2]

Normalization can create auxiliary nonterminals. They simplify rule shape while making source-grammar explanations less immediate. A tooling pipeline should preserve a mapping from helper rules back to source productions if users need interpretable parses.^[3]

Abstract Reasoning¶

CNF separates three claims that are easily conflated. First, a grammar either passes the production-shape test or it does not. Second, a construction can replace a failing CFG by an equivalent CNF grammar for the same string language. Third, a particular parser may exploit the form. The second does not imply identical derivation histories, and the third is not needed for the first.^[1]^[2]

This distinction makes counterfactual tests precise: leave one A → B rule in place and form-membership fails; replace it by allowed alternatives and membership may be restored; switch from recognizability to weighted parse probability and a new preservation proof is required.

Knowledge Transfer¶

A formal grammar for balanced marker strings and a probabilistic grammar for sentence constituents use unlike terminals, but both can fill the same production roles: binary nonterminal expansions and single-terminal emissions. CNF transfers as an exact grammar-shape test, not a metaphor for “making something binary.” The live Context-Free Grammar carries the wider one-nonterminal-left generative pattern; CNF adds the narrower right-side shapes.^[1]^[2]

Examples¶

Balanced strings. Consider the explicitly constructed grammar S → A B | A C, C → S B, A → a, B → b. Its CFG carrier has start S, nonterminals S,A,B,C, and terminals a,b; all nonlexical rules fill the binary branch role, and A → a, B → b fill single-terminal emission. No empty exception is needed. It generates ab, aabb, aaabbb, and so on, and every written rule passes the CNF test.^[1]

Mapped back: the instance is CNF because the rule inventory itself has the stipulated shapes, not because a conversion algorithm was run. The displayed grammar is a constructed checkable example, not claimed to be Gallier and Quaintance's exact grammar.

Probabilistic phrase-structure parsing. MIT's CNF-style PCFG has syntactic nonterminals as its grammar carrier, weighted X → Y Z rules filling the binary branch, and X → word rules filling terminal emission. The nonempty sentence case does not exercise the empty exception. A chart parser uses the resulting local span-combination pattern.^[2]

Mapped back: rule probabilities are additional annotations; the production shapes establish CNF. This is an example of a PCFG in the form, not a proof that arbitrary probabilistic conversion retains the same distribution.

Negative boundary. An unbinarized rule A → B C D is still a valid context-free production because its left side is one nonterminal, yet it fails CNF's binary-role test. Its generated strings could still have a different CNF grammar.^[1]^[3]

Structural Tensions¶

Uniform binary form versus readable source productions. Binarization enables a regular parser recurrence but inserts helper categories and can obscure which original phrase rule was used. Diagnostic: Can a normalized derivation be mapped back to the source rule without guessing?^[3]
String-language equivalence versus derivation fidelity. The standard conversion preserves the set of generated strings, but source parse trees may be reorganized, and weighted parses need additional care. Diagnostic: Does the claim concern accepted strings, parse trees or probability mass on those trees?^[1]^[2]
Empty-word coverage versus simple rule inspection. Omitting ε makes the rule inventory simpler but excludes the empty word; allowing S → ε covers that word but requires guarding the start symbol's right-side appearances. Diagnostic: Is the claimed grammar assessed under a declared empty-string convention?^[1]

Structural–Framed Character¶

CNF is strongly structural within formal grammar theory: the production inventory either satisfies the stated syntactic test or not. Its evaluative weight is instrumental, not an assertion that the grammar is better; the form aids certain proofs and parsers but can make a source grammar less readable. Its human-practice dependence lies in selecting a grammar, notation and use case, while membership in the stated rule class follows mechanically from those choices. Its institutional origin is formal-language theory, not a social authority that decides validity by decree. Its vocabulary travel reaches unlike formal-language and language-processing settings only where genuine CFG productions and the same right-side tests appear. Import versus recognition requires identifying those rules; calling any binary tree “CNF” without a CFG imports terminology rather than recognizing the structure.

Live Formal System (Formal System) supplies the broad portable skeleton of symbols and transformation rules, through the live Context-Free Grammar genus: one nonterminal is rewritten regardless of surrounding symbols. CNF tightens the allowed replacement forms. No new direct edge to Formal System is proposed. Its character: a precise formal-grammar subtype with operational uses, not a general claim about binary organization in all domains.

Structural Core vs. Domain Accent¶

What is skeletal. The broad prime-level skeleton is a Formal System of symbols and transformation rules; the immediate strict parent is live Context-Free Grammar, with a start symbol and one-nonterminal-left productions generating strings through derivations. CNF cannot exist without that formal production system, and its binary/lexical rules are still CFG productions.

What is domain-bound. The right sides must be exactly two nonterminals or one terminal, except for the declared start-rule empty case. Formal-string and natural-language terminals, probabilities, helper names, conversion steps, and parsing algorithms can vary; the rule-shape test cannot. Remove it and the entry collapses to CFG in general.

Why this is not a prime. CFGs themselves have a recognizable formal-language substrate. CNF is narrower still: it applies only where that substrate is represented as productions with these exact shapes. A binary decision tree may be structurally similar, but it is not a CNF grammar absent nonterminal/terminal derivations. The larger abstraction is the generative formal system, not this named grammar normal form.

This entry is a kind of Context-Free Grammar.

DAG parent: live Context-Free Grammar (Context-Free Grammar). CNF inherits its generative system and restricts production right sides. The live Chomsky Hierarchy concerns expressive classes, while Kuroda Normal Form has a different rule system; neither is an alternative strict parent merely because its title shares formal-language vocabulary.

Relationships to Other Abstractions¶

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

Chomsky Normal Form → Context-Free Grammar → Formal System → Formalization → Representation → Abstraction

Show alternative path (1)

Neighborhood in Abstraction Space¶

Chomsky Normal Form sits in a moderately populated region (50^th 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

Not to Be Confused With¶

An arbitrary CFG. It may contain unary, empty or long rules. Tell: inspect every production, not only the language it generates.^[1]
A CNF conversion algorithm. It is a route to the form, not the form itself. Tell: is the claim about the grammar's current rules or about operations performed on them?^[1]
A CNF-enabled parser. Its chart recurrence exploits the form but is a separate procedure. Tell: would the grammar remain CNF if no parser ran?^[2]

References¶

[1] 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. Definition, empty-word convention and language-preserving conversion theorem. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t

[2] MIT OpenCourseWare 6.864, "Advanced Natural Language Processing," Lecture 4 (2005), PDF p. 18. CNF-style weighted rule forms and qualified chart-parsing complexity. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i

[3] Cornell CS6741, "Parsing" lecture notes (2015), PDF pp. 33–53. Worked phrase-structure simplification and binarization. registry ↩a ↩b ↩c ↩d