Detecting and explaining (in-)equivalence of context-free grammars
summary
A scalable framework decides, proves, and explains many (in-)equivalences of context-free grammars despite undecidability by combining a new pattern-based transformations language, theory-backed algorithms for bounded-language equivalence (polynomial-time boundedness checks and Parikh-image formulas), graph-inspired grammar canonization, bug-fixing transformations, and caching. An implementation integrates into tutoring systems, evaluates 55,000 student attempts, reduces manual review to about 260 clusters (~4%), and runs on real course data across two semesters.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:43Grammar feedback in education
- 2:20Grammar equivalence challenges
- 3:24Normalization framework
- 4:50Normalization pipeline
- 6:18Error explanation transformations
- 7:23Bounded languages feedback
- 8:25Equivalence decidability
- 10:54Framework integration
- 11:37Basic grammar tests
- 12:19Equivalence via bounded witnesses
- 12:40Manual review and caching
- 13:22Evaluation on student data
related talks
17mIterative-Epoch Online Cycle Elimination for Context-Free Language Reachability
12mAutomatic Grammar Repair
31mPyrosome: A Framework for Modular, Extensible, Equivalence-Preserving Compilati...
20mEquivalence by Canonicalization for Synthesis-Backed Refactoring
31mSemantics-preserving Transformation of Context-free Grammars into LL(1) Form
15mRecursive State Machine Guided Graph Folding for Context-Free Language Reachability
29mGrammar Inference for Ad Hoc Parsers
24mAutomated extraction of grammar optimization rule configurations in a metamodel-gr...