Automated grading of DFA constructions

One challenge in making online education more effective is to develop automatic grading software that can provide meaningful feedback. This pa-per provides a solution to automatic grading of the standard computation-theory problem that asks a student to construct a deterministic finite automa-ton (DFA) from the given description of its lan-guage. We focus on how to assign partial grades for incorrect answers. Each student’s answer is com-pared to the correct DFA using a hybrid of three techniques devised to capture different classes of errors. First, in an attempt to catch syntactic mis-takes, we compute the edit distance between the two DFA descriptions. Second, we consider the en-tropy of the symmetric difference of the languages of the two DFAs, and compute a score that es-timates the fraction of the number of strings on which the student answer is wrong. Our third tech-nique is aimed at capturing mistakes in reading of the problem description. For this purpose, we con-sider a description language MOSEL, which adds syntactic sugar to the classical Monadic Second Or-der 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 in-correct 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 pre-ferred over the human graders for both scalability and consistency.