Correcting Deterministic Finite Automata for Didactic Feedback

Abstract

Motivated by educational applications, we study the problem of computing all corrections that transform a finite automaton into one recognizing a given regular language L. We show that for deterministic finite automata the set of all corrections can be finitely characterized as a regular tree language. The construction is based on a tree encoding of all deterministic finite automata recognizing L, which is extended to correction trees that make individual corrections and their induced edit-operations explicit. Leveraging the closure properties of regular tree languages, we introduce so-called filters for selecting corrections satisfying didactic constraints, enabling the derivation of individualized feedback from student submissions.