Module
Context-Free Grammars and Context-Free Languages
Sign in to add this module to your path and practice.
About
CFGs: variables, terminals, productions, derivations (leftmost), parse trees, ambiguity. Context-free languages. Designing grammars for classic CFLs (balanced parentheses, aⁿbⁿ, simple programming constructs). Chomsky normal form (CNF) for later algorithms/proofs.
Goal
Write unambiguous and ambiguous CFGs for standard languages; relate derivations and parse trees; convert a CFG to CNF; recognize the extra power of CFLs over regular languages (one unbounded counter / stack discipline).
Unlocks
Tutor
Ask questions about this module.
Hi — I'm your tutor for Context-Free Grammars and Context-Free Languages. Ask about the concepts, goal, or where you're stuck.