Educational game and Intelligent Tutoring System that can be used in a Languages and Automata (Theory of Computation) course. Honors thesis for a Wellesley College Bachelor of Arts in Computer Science. Includes two activities spanning three "worlds" of increasing difficulty. Uses Bayesian Knowledge Tracing to estimate students' mastery of each activity and determine whether they are allowed to move to the next "world".
In this activity, students construct Deterministic Finite-State Automata (DFAs) to recognize a variety of regular languages.
The three "worlds" have associated difficulty levels of languages to recognize.
The student's DFA must end in an accept state for a sample string in the language, and end in a non-accept state for a sample string not in the language.
The system can generate hints using graph similarity and a Markov Decision Process:
- Cluster prior student DFAs for the same language by graph similarity.
- Identify the cluster to which the student's current in-progress DFA belongs.
- Get all next steps that prior students took from the current graph cluster.
- Use an MDP to identify the next step that was most likely to lead to a correct final DFA.
In this activity, students make a series of choices to construct a proof using the pumping lemma that a given language is not regular. For example, one choice the student makes is to choose a reason why a particular string is a counterexample to the assertion that the language is regular.
