### Automated Grading of DFA constructions

### Abstract

One challenge in making online education more effective is to develop automatic grading software
that can provide meaningful feedback. This paper provides a solution to automatic grading of the
standard computation-theory problem that asks a
student to construct a deterministic finite automaton
(DFA) from the given description of its language.
We focus on how to assign partial grades for
incorrect answers. Each student’s answer is compared
to the correct DFA using a hybrid of three
techniques devised to capture different classes of
errors. First, in an attempt to catch syntactic mistakes,
we compute edit distance between the two
DFA descriptions. Second, we consider the entropy
of the symmetric difference of the languages of the
two DFAs, and compute a score that estimates the
fraction of the number of strings on which the student
answer is wrong. Our third technique is aimed
at capturing mistakes in reading of the problem description.
For this purpose, we consider a description
language MOSEL, which adds syntactic sugar
to the classical Monadic Second Order Logic, and
allows defining regular languages in a concise and
natural way. We provide algorithms, along with optimizations,
for transforming MOSEL descriptions
into DFAs and vice-versa. These allow us to compute
the syntactic edit distance of the incorrect answer
from the correct one in terms of their logical
representations. We report an experimental study
that evaluates hundreds of answers submitted by
(real) students by comparing grades/feedback computed
by our tool with human graders. Our conclusion
is that the tool is able to assign partial grades
in a meaningful way, and should be preferred over
human graders for both scale and consistency.