3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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:

  1. Many students don't think to test the smallest possible machines (e.g. one state, either as accept or not)
  2. NFAs are harder than they sound. I specify a maximum depth (such as 50 rounds) to prevent infinite looping on epsilons.
  3. 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.
$\endgroup$
3
  • $\begingroup$ Thanks for sharing. Do you use any automated grading system for the submissions? $\endgroup$ Commented May 22, 2023 at 11:43
  • 1
    $\begingroup$ @DrimadesBoy They're console programs, so not really, though I do have both lab writeups and test cases that I wouldn't mind sharing with another instructor if there were a way to reach each other off network. $\endgroup$
    – Ben I.
    Commented May 22, 2023 at 12:05
  • $\begingroup$ I would love to take a look drimades77(at)gmail.com. Thank you! $\endgroup$ Commented May 22, 2023 at 17:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.