0%
Theory of Automata & Formal Languages
Convert any CFG to Chomsky Normal Form or Greibach Normal Form with step-by-step transformations, CYK parsing, FIRST/FOLLOW sets, and parse tree visualization.
A comprehensive toolkit for grammar transformations, parsing, and visualization
ε-elimination, unit removal, and binarization in 6 detailed steps
CoreLeft-recursion elimination and terminal substitution in 9 steps
CoreString membership testing with visual triangular parsing table
ParsingTabular computation of FIRST and FOLLOW for every variable
AnalysisCanvas-rendered trees with leftmost derivation tracing
VisualBefore/after comparison, clipboard copy, and .txt export
UtilityFrom grammar input to fully converted normal form
Type productions directly or use the structured form. Load built-in examples to get started quickly.
Select CNF, GNF, or both. The converter applies each transformation step-by-step with full explanations.
Test strings with CYK parsing, view FIRST/FOLLOW sets, explore parse trees, and export your results.
Understanding Context-Free Grammars and their standard transformations
A Context-Free Grammar consists of rules where a single non-terminal variable expands into any sequence of variables and terminals. It is heavily used in compiler design, string parsing, and defining programming language syntax.
In CNF, every production rule expands a variable into exactly two variables, or into a single terminal. This strictly binary structure enables efficient algorithms like CYK to parse a string of length n in O(n³) time.
In GNF, every production rule starts with exactly one terminal symbol, followed by zero or more variables. This form guarantees that each step consumes one input character, which is ideal for top-down parsers and Pushdown Automata.
Drop an image here or
Supports PNG, JPG, JPEG, BMP, WebP
Click the microphone to start speaking
Try saying "S produces small a capital B"
| Variable | FIRST | FOLLOW |
|---|
Every production has the form A → BC or A → a.
Test if a string belongs to the language using the CYK algorithm on the CNF grammar.
Every production has the form A → aα where α ∈ V*.
Test if a string belongs to the language using top-down parsing on the GNF grammar.