i'm a new instructor & also new here.

How do you teach Theory of Automata / Formal Language Theory / Computation Complexity?

Is it theory only, or including programming? If theory only, how deep - for example, are they supposed to be able to prove, how deep? If programming, what kind?

It would be much appreciated if you can share your wisdom. If there're other similar threads, would appreciate it very much if you can share the link. I'm also still reading the threads here, and browsing the internet for the syllabus of other universities. I don't have any TA, and nobody to discuss about this course in my department (theoretical CS is mostly non-existent here, most focus on application).

Thank you very much.

  • 2
    $\begingroup$ Hello, and welcome to Computer Science Educators. I hope you have found the site helpful so far. You have the needed reputation points to join The Classroom, our often quiet, chatroom. I am thinking this question might be a bit broad in scope for the site. The problem is not, however. Things tend to work best when a questions has "A" question rather than a group of questions. Responses are more focused, and answers more helpful. $\endgroup$ – Gypsy Spellweaver Mar 13 at 7:32
  • $\begingroup$ This question can probably be split into really good questions, which are a better fit for the Q&A system of this site. $\endgroup$ – ItamarG3 Mar 13 at 9:22
  • $\begingroup$ Thank you for the comments and the chatroom. I'll edit again later if I manage to split the question down. $\endgroup$ – kate Mar 13 at 9:50
  • $\begingroup$ I teach computational theory, but I'm not sure how to approach this question. You have a wide degree of latitude depending on the goals of the course, which either you, your department, your school, or your state get to set. What do you want your students to get out of the course? What are the key ideas you want them to understand? What do you hope they will be able to do with it? $\endgroup$ – Ben I. Mar 13 at 17:35

The course is often theoretical, taught like a math course, which it is, actually. In fact, my daughter has a doctorate in Philosophy and this was one of her doctoral courses since it relates to Epistemology.

There is actually more material than can be covered in a single course, I think. Formal language theory could be introduced as part of a Languages and Compilers sequence to separate it out a bit. This is how I taught formal languages so as to motivate scanners and parsers.

Automata and Computability is quite a lot on its own.

There is a third way to teach the course, actually, which is to teach the insights, rather than going through the proofs. What does it all actually mean if you look at it from a bit of a distance. What does it mean for problems to be equivalent?

But if you want to have a course that includes programming, you should at least look at JFlap, which is a system for teaching the course and was developed by Susan Rodger at Duke. The system lets you simulate finite automata and can support either a theoretical or insight driven course.

There are a couple of old books, now somewhat hard to find, that I consider classics and excellent introductions. Both are by V. J. Rayward-Smith:

A First Course in Formal Language Theory

A First Course in Computability

These are both small books but are good for the basics and for generating insight. They are worth having, even if you don't use them as course texts.

There have been a lot of books published since I studied this subject. If I had to teach a complete course, the first book I would consider would be Introduction to the Theory of Computation by Michael Sipser. I expect it would be clear and deep.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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