Synthesis of regular expression problems and solutions

摘要

Formal languages and automata (FLA) theory is perceived by many as one of the hardest topics to teach or learn at the undergraduate level, due to the abstract nature of its contents; often containing proofs, lots of symbolic notations, and specifications of abstract computing machines that are difficult for many students to relate with. One way of approaching this problem is to administer numerous practice problems to students to aid learning. In this paper, we present: definitions of formal rules (using context-free grammar notations) for the synthesis of practice problems and solutions in a sub-domain of formal language theory - regular expressions, new algorithms for implementing these rules with iterations of generated problem instances and associated solutions. Generated problems are then embedded in predefined, short text response and multiple-choice question templates. The implementation of this technique produced numerous problems and solutions that can be used as practice, test or examination questions to support the teaching of regular expressions as a topic in FLA at the undergraduate level.