Detecting and Explaining In-Equivalence of Context-Free Grammars

Explore a 15-minute conference presentation from OOPSLA 2025 that introduces a scalable framework for determining and explaining the equivalence or inequivalence of context-free grammars. Learn about innovative techniques that combine abstract grammar transformation languages, theory-based comparison algorithms, and graph-theory-inspired grammar canonization to efficiently identify isomorphic grammars. Discover how researchers from Ruhr University Bochum and the University of Oxford tackle the generally undecidable equivalence problem for context-free languages by developing methods that successfully handle large portions of real-world datasets collected from educational support systems. Examine the implementation and evaluation of this framework, which addresses critical challenges in intelligent tutoring systems by providing automated detection and explanation capabilities for grammar equivalence. Gain insights into the interdisciplinary approach that bridges formal language theory, educational technology, and computational methods to create practical solutions for comparing context-free grammars at scale.