Context-Free Grammar Simulator
Generates context-free languages · Equivalent to PDA
Grammar is auto-converted to CNF before running.
+ added− removed
Original Grammar
The grammar as entered, before any transformation.
S→a S b | a b
Step 1 — New Start Symbol+1
S appeared on the right-hand side of a rule, so a fresh start symbol _S0 → S was introduced to ensure S is never on a RHS.
S→a S b | a b
_S0→S
Step 2 — Eliminate ε-ProductionsNo change
Remove rules that derive the empty string. For each rule containing a nullable symbol, add a version with that symbol omitted.
Step 3 — Eliminate Unit Productions+2−1
Replace rules of the form A → B (single non-terminal) by copying all non-unit rules reachable from B into A.
Unit closures: _S0 ⟹* { _S0, S }
S→a S b | a b
_S0→a S b | a b | S
Step 4 — Binarize Long Rules+4−2
Split rules with 3 or more symbols into cascading binary rules using fresh non-terminals.
S→a _B0 | a b | a S b
_S0→a _B1 | a b | a S b
_B0→S b
_B1→S b
Step 5 — Wrap Terminals in Binary Rules+8−6
In binary rules, replace each terminal with a fresh non-terminal that produces exactly that terminal.
S→_T_a _B0 | _T_a _T_b | a _B0 | a b
_S0→_T_a _B1 | _T_a _T_b | a _B1 | a b
_B0→S _T_b | S b
_B1→S _T_b | S b
_T_a→a
_T_b→b
Want a specific preset configuration added? Request it by email at contact@csvisualizer.com.