Context-Free Grammar Simulator

A context-free grammar is a formal grammar with production rules that replace a single non-terminal symbol with a string of terminals and non-terminals. CFGs describe context-free languages and are widely used to define the syntax of programming languages. They are strictly more expressive than regular grammars (DFA/NFA).

Chomsky Normal Form is a restricted form of CFG where every rule is either A → BC (two non-terminals) or A → a (one terminal). Any CFG can be converted to CNF without changing the language it generates. CNF is required by the CYK algorithm used in this simulator.

The Cocke–Younger–Kasami (CYK) algorithm is a dynamic programming algorithm that decides whether a string belongs to a context-free language. It fills an n×n triangular table of substrings bottom-up and runs in O(n³ · |G|) time, where n is the input length and |G| is the grammar size.

A derivation tree (or parse tree) shows how a string is derived from the start symbol step by step. Each internal node is a non-terminal, each leaf is a terminal character, and the children of each node match the right-hand side of the production rule applied at that step. This simulator reconstructs one valid derivation tree whenever the input is accepted.

CFGs describe context-free languages, which properly include all regular languages. Classic non-regular examples are {aⁿbⁿ | n ≥ 1} (equal counts of a and b), balanced parentheses, and arithmetic expressions. However, CFLs cannot describe {aⁿbⁿcⁿ} — that requires a more powerful model such as a Turing machine.