A browser-based tool that simplifies Context-Free Grammars by removing useless symbols, with step-by-step visualization and language preservation verification.
cfg-simplifier/
├── index.html — Page structure and UI markup
├── style.css — All visual styling and animations
├── script.js — Full CFG algorithm and rendering logic
└── README.md — This file
No build tools or servers needed. Just open index.html in any modern browser:
# Option 1: Double-click index.html in your file manager
# Option 2: Via terminal
open index.html # macOS
xdg-open index.html # Linux
start index.html # Windows- One production rule per line
- Use
->to separate variable from productions - Use
|to separate alternative productions - Variables must be single uppercase letters (A–Z)
- Terminals must be lowercase letters or symbols
Example:
S -> AB | a
A -> aA | a
B -> C
C -> c
Converts the raw text input into an internal grammar object:
{ S: ["AB", "a"], A: ["aA", "a"], B: ["C"], C: ["c"] }A variable is generating if it can eventually derive a string of terminals.
Rules for each symbol s in a production:
sis lowercase → terminal ✓sis uppercase but has no rule → not generating ✗sis uppercase and already confirmed generating → ✓
This fixed-point iteration repeats until no new generating symbols are added.
- Remove all variables not in the generating set
- Remove all productions that reference non-generating variables
BFS from the start symbol through all productions. A variable is reachable if it can be reached from the start symbol via any sequence of productions.
Variables not reached in Step 4 are dropped.
The grammar after both passes contains only useful symbols — those that are both generating and reachable.
BFS string generation (up to length 6, max 25 strings) is run on both the original and simplified grammar. If the sampled string sets match, the language is considered preserved.
⚠️ This is an approximate check. It cannot prove full language equivalence for infinite languages.
The key insight used throughout the algorithm:
if (s.toLowerCase() === s) return true; // lowercase → terminal ✓
if (!grammar[s]) return false; // uppercase, no rule → not generating ✗
return generating.has(s); // must already be confirmed generatingThis handles the critical edge case where a variable appears on the RHS of a production but has no rule of its own — it must be treated as non-generating and propagate that status upward through the dependency chain.
- Bright, clean light-blue theme with soft shadows
- Step indicator that activates as each algorithm phase completes
- Color-coded symbol tags:
- 🟢 Green — generating
- 🔵 Blue — reachable
- 🔴 Red — removed / non-generating
- ⚫ Gray — unreachable
- Struck-through rules showing what was eliminated
- Staggered card reveal animations
- Side-by-side string comparison for verification
This tool implements the useless symbol elimination algorithm from formal language theory (Theory of Computation / Automata Theory).
A symbol is useless if it is either:
- Non-generating — cannot derive any terminal string, or
- Unreachable — cannot be reached from the start symbol
Removing useless symbols does not change the language generated by the grammar.
Reference: Hopcroft, Motwani & Ullman — Introduction to Automata Theory, Languages, and Computation (Chapter 7)
| Input | Expected Simplified |
|---|---|
S -> AB | a / A -> aA | a / B -> C / C -> c |
S -> AB | a, A -> aA | a, B -> C, C -> c (all generating) |
S -> AB | a / A -> aA | a / B -> X (X has no rule) |
S -> a, A -> aA | a (B is non-generating) |
S -> a / A -> b |
S -> a (A is unreachable) |
Works in all modern browsers. No external dependencies — all logic is plain JavaScript (ES6+). Google Fonts used for typography (requires internet connection for optimal display; falls back gracefully).