Convert a context-free grammar one stage at a time
This CFG to CNF converter rewrites a context-free grammar into strict Chomsky normal form. Edit the loaded grammar and the result updates immediately. The page shows the final rule count and fresh start symbol, then lets you inspect every intermediate grammar. Open What changed to compare the rules added and removed at the selected stage. Copy final CNF always copies the completed grammar, even while you are viewing an earlier stage.
CNF is useful when a later algorithm expects a restricted grammar shape. The main example is CYK membership testing, which combines two previously recognized spans at a time. Conversion changes the grammar's structure while preserving its terminal strings. It does not promise to preserve production numbers, parse-tree shapes or how many trees the original grammar had for a particular word.
Enter spaced symbols and an explicit empty alternative
Write one rule per line, such as S -> A S A | a B. The vertical bar separates alternatives. Spaces separate symbols, so ASA is one symbol while A S A is three. A symbol appearing on any left side is a nonterminal; other symbols are terminals. The first rule identifies the original start symbol. Alternative arrow spellings shown by related grammar tools are also accepted.
Write ε, epsilon or another supported empty spelling as the entire alternative. Do not write a ε to mean a followed by nothing, and do not leave an alternative blank after a vertical bar. The page reports these cases with a line number and a suggested spelling. Empty input is an error rather than an invented default grammar. Conversion is bounded to keep a classroom-sized exercise responsive; a nullable rule with many optional positions can expand rapidly.
Add a fresh start before removing epsilon rules
The converter first introduces a new start symbol whose only initial rule points to the old start. This fresh symbol never appears on a right side. It matters when the old start appears recursively inside other rules, and when the language includes the empty string. Fresh names avoid existing terminals as well as nonterminals, so a terminal that happens to look like a helper name is not silently reclassified.
A nullable nonterminal can derive the empty string. The converter finds the complete nullable set by repeated scans: a left side becomes nullable when every symbol on an alternative is already nullable, with an empty right side satisfying that condition immediately. It then generates the distinct alternatives obtained by omitting any combination of nullable occurrences. Empty alternatives are retained only for the new start symbol.
Follow unit chains before changing long rules
A unit rule has exactly one nonterminal on its right side. Removing just visibly adjacent unit rules is not enough: chains can be indirect, and cycles can return to the same symbol. For each left side, this converter follows the reachable unit symbols using a visited set and inherits their non-unit alternatives. The visited set prevents a unit cycle from creating an endless conversion.
After unit elimination, a long right side is replaced with a binary chain. The chain uses fresh helpers and keeps the original symbol order. The final stage replaces terminals occurring inside binary rules with fresh terminal-producing variables. Rules that already produce one terminal do not need that replacement. These stages are intentionally separate so the selected grammar and rule differences explain why a helper appeared.
Worked nullable and unit-rule example
The loaded exercise is:
S -> A S A
S -> a B
A -> B
A -> S
B -> b
B -> ε
Its nullable symbols are B and A. The original start is not nullable, so the completed grammar has no start-to-empty alternative. The conversion creates fresh start S0 and finishes with 21 alternatives. This result is generated by the converter itself, including helper names and alternative order:
S0 -> A N2 | S A | A S | T B | a
S -> A N | S A | A S | T B | a
A -> A N1 | S A | A S | T B | a | b
B -> b
N -> S A
N1 -> S A
N2 -> S A
T -> a
For example, omitting nullable outer occurrences from A S A creates A S, S A and S as well as retaining A S A. The temporary S-to-S unit alternative is removed by unit closure, not treated as a terminal production. In a handwritten answer, a different consistent choice of helper names can represent the same converted language.
Understand the final CNF check
Every final nonempty production must have one terminal or two nonterminals on its right side. Only the fresh start may produce ε, and that start cannot occur on any right side. The completed grammar is checked by the same strict validator used by the site's CYK library. A passing check establishes the required rule shape; it is distinct from testing whether a particular string belongs to the language.
Some symbols can remain declared without productive rules. A grammar consisting only of an unproductive unit cycle generates no terminal strings. For that case the page explicitly displays an empty-language message and no final productions; copying that explanation does not create a textual grammar that you can paste back as an epsilon rule. Empty language and a language containing the empty string are different outcomes.
Avoid common conversion mistakes
Keep the original terminal order when introducing binary helpers. Do not drop combinations when a nullable symbol occurs more than once in the same rule. Do not retain a non-start epsilon production, or accidentally leave a single-nonterminal unit rule in the completed grammar. A production with two terminals is not strict CNF merely because its length is two.
The tool removes duplicate alternatives but does not attempt a smallest equivalent grammar. It does not remove left recursion as an LL parser preparation step, construct a Greibach normal form grammar or prove ambiguity. Those are different tasks. Conversion can increase the number of rules, so a longer answer does not by itself mean the conversion failed.
Continue with a membership or parsing exercise
Use the CYK parser to test a word with the completed grammar and inspect its triangular table. The CYK worked example explains how split points combine shorter spans. The parse tree generator explores derivations in an original grammar, while the compiler lab groups the related tools. Keep a copy of the original rules when you need to compare tree structure rather than language membership.