I am scheduled to teach a "Computer Science Theory" course. Topics include: Turing Machines, Languages, Automata (DFA, NFA), etc. I would like to make it less boring and more practical for students. My idea is to add some coding assignments where students are required to program (Python, Java) some of the machines used in the course. Some hints/suggestions/materials would be very useful and appreciated. Does anyone have such experience or do you know of any course applying similar approach?
My course takes this approach. I have the students create a DFA and an NFA runner, and later, a TM runner as well. We skip PDAs - they turned out to be monstrously difficult for the students to deal with. It turns out that implementing nondeterministic stacks is just a bit too abstractly difficult for many of my students.
I will give you warning of a few traps:
- Many students don't think to test the smallest possible machines (e.g. one state, either as accept or not)
- NFAs are harder than they sound. I specify a maximum depth (such as 50 rounds) to prevent infinite looping on epsilons.
- Turing Machines are relatively easy to code up. What's nice is to give them something to actually code up on them. I've created a little competition, which I've earlier outlined here.