ToolSphere

CFG to CNF Converter

Computer science

Convert a context-free grammar to strict Chomsky normal form, with nullable rules, unit closure, fresh helpers and each intermediate grammar explained.

Edit one rule per line, with spaces between symbols; ε means the empty string.

CNF ready: 21 rules · start S0

CNF means one terminal (token) or two nonterminals (grammar variables) per rule; only the fresh start may produce ε.

Copy final CNF

5. Isolate terminals in binary rules

A terminal inside a binary rule is replaced by a fresh variable with a terminal-only rule. Single-terminal rules stay unchanged.

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
What changed: 4 added, 3 removed
+ S → T B
+ A → T B
+ S0 → T B
+ T → a
− S → a B
− A → a B
− S0 → a B

The first rule chooses the original start. Helper names are fresh. This conversion preserves strings, not original tree shapes or ambiguity counts. Continue with the CYK parser to test a string.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use CFG to CNF Converter

  1. 1Edit the loaded grammar with one rule per line and spaces between symbols.
  2. 2Use ε for an empty alternative; the first rule chooses the original start.
  3. 3Read the final CNF status and select a conversion stage.
  4. 4Expand What changed to compare added and removed rules.
  5. 5Copy the final grammar and test a string with the CYK parser.

About CFG to CNF Converter

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.

Guides and tutorials

Frequently asked questions

What is Chomsky normal form?

Strict CNF uses one terminal or two nonterminals per nonempty production. Only the fresh start may produce the empty string, and that start never appears on a right side.

Does CFG to CNF conversion preserve the language?

The conversion is designed to preserve the terminal strings, including the empty string when the original start is nullable. It changes tree structure and introduces helper variables.

How do I type a grammar into the converter?

Use one left-side symbol per rule and spaces between right-side symbols, for example S -> A B | a. The first rule selects the original start symbol.

How do I enter epsilon?

Write ε or epsilon as the whole alternative. A blank alternative or epsilon beside other symbols produces an actionable error.

Why is a new start symbol necessary?

It separates the start from recursive right-side occurrences and allows a start-only epsilon rule. Fresh naming also prevents collisions with existing grammar symbols.

How are nullable rules removed?

The tool finds all nullable nonterminals, then adds every distinct omission combination before removing non-start empty rules. Repeated occurrences can create several combinations.

What happens to unit-production cycles?

Unit reachability is computed with a visited set, so cycles terminate. Each left side inherits the reachable non-unit alternatives.

Can two terminals appear in a CNF production?

Not in this strict form. Terminals inside a binary right side are replaced by helper nonterminals that each produce one terminal.

Why does my answer use different helper names?

Helper names are arbitrary provided they are fresh and used consistently. This converter uses deterministic names so its steps and copied answer agree.

Does the converter remove ambiguity or left recursion?

It is a language-preserving normal-form conversion, not an ambiguity resolver or an LL grammar rewrite. Use the related parsing and recursion tools for those separate questions.

Have a suggestion for CFG to CNF Converter?Share your feedback ↗