Automata Algorithm Module
For my bachelor project, we extended checkr/inspectify, a teaching tool used in parts of the Computer Science Modelling course, with automata learning environments.
The project added support for the automata pipeline taught in the course: regular expressions, epsilon-NFAs, NFAs and DFAs. Students implement the transformations themselves in F#, generate test inputs, inspect the reference output and get feedback on their own solution through the platform.
The individual algorithms are well-known, so the interesting part was not just implementing Thompson construction or subset construction in isolation. A lot of the work was in turning them into complete learning environments: deciding what students should implement, what feedback they should get, how strict validation should be, what should be visualized, and how the tasks should fit into the existing course setup.
One important design choice was validation. Many automata tools can use language equivalence because the task is usually to manually construct one automaton that accepts the right language. Here, the learning goal was more specific: students were supposed to implement the actual transformations from the course. We therefore used graph isomorphism, so state names could differ, but the structure still had to match the intended algorithm.
I mainly worked on the backend automata module, reference implementations, validation logic, input generation, DOT import/export and the surrounding course integration. We also spent quite a bit of time on usability and feedback loops. Generated automata can quickly become hard to read, so the system supports DOT-based visualization and compaction options to make it easier to compare a student's output with the reference.
The final result was delivered with student-facing task descriptions, student implementation environments, evaluation inputs and integration into the existing tool. One of the nicest outcomes was that the work was not just a prototype: our supervisor told us it is expected to be used in the next course cycle.
More details are in the public version of the defense slides.
What it included
- Reference implementations for the automata transformations
- Random regex input generation for testing student solutions
- Validation using graph isomorphism
- DOT import/export for automata
- Visualization and compaction for larger generated automata
- F# student implementation environments
- Student-facing task descriptions and evaluation inputs for the teaching team