💻 computer science

Detecting and Explaining (In-)equivalence of Context-Free Grammars

This paper proposes a scalable framework that combines abstract grammar transformations, theory-based comparison algorithms, and graph-theory-inspired canonization to effectively decide, prove, and explain the (in-)equivalence of context-free grammars, successfully handling a significant portion of large educational datasets despite the general undecidability of the problem.

Original authors: Marko Schmellenkamp, Thomas Zeume, Sven Argo, Sandra Kiefer, Cedric Siems, Fynn Stebel

Published 2026-04-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marko Schmellenkamp, Thomas Zeume, Sven Argo, Sandra Kiefer, Cedric Siems, Fynn Stebel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a teacher grading homework for a class of computer science students. The assignment is simple: "Write a set of rules (a grammar) that generates a specific pattern of words."

For example, the teacher asks for a grammar that creates words like ab, aabb, aaabbb (where the number of as always equals the number of bs).

A student submits their rules. The computer needs to answer two questions:

Is it right? (Does it generate exactly the right words?)
If it's wrong, why? (Did they forget a rule? Did they add an extra one?)

The problem is that for complex patterns, checking if two sets of rules are "equivalent" is mathematically impossible to solve perfectly for every case. It's like trying to prove that two different recipes will always result in the exact same cake, no matter how you tweak the oven temperature.

This paper presents a smart, scalable framework that acts like a super-tutor. It doesn't just say "Wrong." It tries to figure out why it's wrong and explains it to the student, handling thousands of student submissions efficiently.

Here is how it works, using some everyday analogies:

1. The "Name-Tag" Trick (Canonization)

Imagine two students write the exact same recipe, but one calls the ingredients "Flour" and "Sugar," while the other calls them "Wheat" and "Cane." A dumb computer might think these are different recipes.

Our framework has a "Name-Tag" system. It strips away the specific names and looks at the structure. It realizes, "Oh, both of these are just 'Mix A + Mix B'." It converts both into a standard, neutral format. If the neutral versions match, the computer knows the student got it right, even if they used different variable names.

2. The "Translation" Tool (Grammar Transformations)

Sometimes, a student's grammar is structurally different but logically the same.

Student: "First, add an egg, then mix."
Solution: "Mix, then add an egg." (Wait, that's different! Bad example).
Better Example: "Add an egg, then mix" vs. "Mix, then add an egg" (if the order doesn't matter for the final result).

The framework uses a Translation Tool. It has a library of "equivalence rules." It can say, "I see you wrote the steps in a different order, but mathematically, it's the same as the solution." It transforms the student's messy rules into a clean, standard version to compare them.

3. The "Bug Fixer" (Explaining Mistakes)

This is the most magical part. If the student is wrong, the framework doesn't just say "Error." It tries to fix the bug to see what the student meant to do.

Scenario: The student forgot to stop the recursion (the loop) correctly. They wrote a rule that generates a, aa, aaa... forever, but they meant to stop at aabb.
The Fix: The framework tries a "patch." It says, "If I change this one line from 'stop at nothing' to 'stop at ab', does it match the solution?"
The Result: If the patch works, the system tells the student: "You were very close! You just missed the stopping condition. Here is the specific line that was wrong."

4. The "Pattern Matcher" (Bounded Languages)

Many homework problems in computer science classes involve "bounded" languages—patterns that are predictable, like a followed by b followed by c.

The framework has a special Mathematical Calculator for these specific types of problems. It turns the grammar rules into a math equation (like a spreadsheet formula). It can then solve the equation to prove, with 100% certainty, that the student's rules generate the exact same list of words as the teacher's rules.

5. The "Memory Bank" (Caching)

Imagine you are grading 50,000 homework assignments. You don't want to re-solve the same math problem 50,000 times.

The framework uses a Memory Bank.

If Student A submits a grammar, the system solves it and saves the answer.
If Student B submits the exact same grammar (or a slightly renamed version) 10 minutes later, the system doesn't re-calculate. It just looks in the Memory Bank and says, "I've seen this before. It's correct."
This makes the system incredibly fast, even with huge datasets.

The Big Picture

The authors tested this system on over 55,000 real student attempts from actual university courses.

Success Rate: It could automatically decide if the answer was right or wrong for almost all the attempts.
Human Workload: Because the system is so good at grouping similar answers and fixing small bugs, a human teacher only needs to manually check a tiny fraction of the homework (less than 1% in some cases).
The Goal: To move away from "grading" and toward "teaching." Instead of a red "X," the student gets a helpful note: "Your grammar generates the word 'abb', which shouldn't be there. Check your rule for the second 'b'."

In short, this paper builds a super-smart, tireless teaching assistant that understands the logic behind computer code, spots mistakes, explains them simply, and learns from every student it helps.

Technical Summary: Detecting and Explaining (In-)equivalence of Context-Free Grammars

1. Problem Statement

The paper addresses the challenge of providing automated, high-quality feedback in educational systems for formal languages, specifically for exercises where students must construct Context-Free Grammars (CFGs) to describe a target language.

While testing the equivalence of two CFGs is undecidable in the general case, educational systems require algorithms that can:

Decide equivalence: Determine if a student's grammar $G$ generates the same language as the solution grammar $H$ .
Explain inequivalence: If $L(G) \neq L(H)$ , provide meaningful feedback (e.g., counterexamples, set notation descriptions, or identification of specific modeling errors) rather than just a binary "incorrect" signal.
Scale: Handle large datasets of student submissions efficiently, minimizing the need for manual instructor intervention.

Existing systems often fail to provide feedback because they rely on simple counterexample generation (which may fail to find a counterexample for complex languages) or assume equivalence if no counterexample is found (leading to false positives).

2. Methodology

The authors propose a scalable framework that combines graph-theoretic canonization, rule-based grammar transformations, and algorithms for bounded context-free languages. The framework operates as a pipeline (illustrated in Figure 1 of the paper) involving the following key components:

A. Grammar Canonization (Isomorphism Detection)

Concept: Two grammars are isomorphic if they differ only by the renaming of non-terminals or the reordering of productions.
Implementation: The framework converts a CFG into a graph and computes a canonical representative using the state-of-the-art graph isomorphism tester bliss.
Function: If a student's grammar is isomorphic to a previously seen grammar (or the solution), it is immediately classified. This handles trivial variations in naming conventions.

B. Grammar Transformation Framework

This component uses a pattern-based language to identify and transform grammars. It serves two distinct purposes:

Normalization (Equivalence): A set of equivalence transformations (e.g., removing redundant productions, standardizing recursion patterns like $a^*$ ) is applied to generate a set of "normalized" grammars. If the normalized sets of the student's grammar and the solution overlap, they are deemed equivalent.
Bug-Fixing (Explanation): A set of "bug-fixing" transformations is applied to incorrect grammars. If applying a transformation (e.g., correcting a missing base case in recursion) makes the grammar equivalent to the solution, the system identifies the specific mistake and generates an explanation (e.g., "You missed the base case $\epsilon$ ").

C. Algorithms for Bounded Context-Free Languages

Approximately half of the languages in introductory courses are bounded languages (languages where $L \subseteq w_1^* \dots w_k^*$ for some words $w_i$ ).

Decision Procedure: The framework implements algorithms derived from Ginsburg and Spanier [12] and Verma et al. [36] to decide equivalence for bounded languages.
Mechanism:
1. Compute a boundedness witness ( $w_1, \dots, w_k$ ) for the solution.
2. Check if the student's grammar is bounded by the same witness.
3. Construct Presburger Arithmetic formulas representing the Parikh images of both languages relative to the witness.
4. Use a Presburger solver (e.g., Princess) to check the equivalence of these formulas.
Explanation Generation: If inequivalent, the framework simplifies the Presburger formulas into human-readable set notation (e.g., $\{a^n b^m \mid n > m\}$ ) to explain the structural difference.

D. Caching and Clustering

To ensure scalability:

Caching: Results of equivalence tests and explanations are cached.
Clustering: Student submissions are grouped into clusters based on equivalence. If one representative of a cluster is proven equivalent (or inequivalent) to the solution, all grammars in that cluster inherit the classification. This drastically reduces the number of manual checks required.

3. Key Contributions

Scalable Framework: A unified system that combines multiple techniques (canonization, transformations, bounded language algorithms) to handle the undecidable problem of CFG equivalence in a practical, high-success-rate manner.
Explainable AI for Education: The ability to generate high-level explanations for incorrect submissions, including:
- Counterexamples.
- Set notation descriptions of the student's actual language.
- Identification of specific "buggy" patterns (e.g., wrong recursion termination).
Pattern-Based Transformation Language: A declarative language for specifying grammar transformations that allows for both normalization (for equivalence checking) and bug-fixing (for feedback).
Explicit Algorithms for Bounded Languages: The authors engineer explicit, constructive algorithms for testing equivalence of bounded languages, filling a gap where previous literature provided only non-constructive proofs.

4. Evaluation Results

The framework was evaluated on 55,667 student attempts across 67 exercises from the educational systems AutomataTutor and Iltis.

Equivalence Detection (RQ1):
- For 45,458 incorrect attempts, the framework proved inequivalence for all but 7.
- For 10,209 correct attempts, the framework automatically proved equivalence for 9,113.
Manual Effort Reduction (RQ2):
- Only 260 grammars (less than 0.5% of total attempts) required manual evaluation by an instructor to classify the entire dataset.
- Only 7 exercises required manually evaluating more than 10 grammars.
Explanation Quality (RQ3):
- High-level explanations were generated for >34,000 of the 45,458 incorrect attempts.
- Explanations included set notation descriptions (for bounded languages) and bug-fixing hints.
Efficiency (RQ5):
- Simple tests (emptiness, finiteness, isomorphism) run in milliseconds.
- Complex tests (bounded language equivalence) take seconds but are heavily optimized via caching.
- Caching significantly reduced computation costs, with >84% of equivalent attempts in a new dataset being found in the cache of a previous dataset after normalization.

5. Significance

This work bridges the gap between theoretical computer science (where CFG equivalence is undecidable) and practical educational technology.

Pedagogical Impact: It enables "intelligent tutoring systems" to provide immediate, personalized, and constructive feedback, shifting the educational model from information delivery to sense-making.
Scalability: It demonstrates that even for undecidable problems, a combination of heuristics, specific algorithmic classes (bounded languages), and caching can solve real-world problems at scale.
Research Foundation: The framework provides a tool for CS education researchers to systematically analyze student misconceptions by clustering errors based on the transformation rules that fix them.

In summary, the paper presents a robust, implementable solution that makes automated grading and feedback for context-free grammar construction feasible and effective, significantly reducing the workload for instructors while improving the learning experience for students.