Automatic Problem Creation

Abstract

Formal Languages and Automata is a common class taken by undergraduates in CS that teaches students about computability theory. Many iterations of this course use problems from a few main textbooks, so this leads to limited variety and more difficulty in guaranteeing academic integrity. This project is a tool that automatically generates construction problems for DFA’s, one of the main types of problems in this class. The problems are generated using MOSEL, a representation of monadic second-order logic, that uses high-level logic to express the problems so they can be easily translated into natural language. The MOSEL syntax tree is generated using fuzzing techniques, applying a ruleset that enforces reasonable and concise problems. The system for problem generation is robust, producing a large number of reasonable and unique problems, and configurable with respect to verbosity and desired level of difficulty.