5
$\begingroup$

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.

Edit: I wonder how other professors/TAs managed to give programming assignments to their students, such as building a CYK algorithm-based parser, but they provided the parser/compiler/backbone (?).

Improve this question
$\endgroup$
5
  • 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
    Commented Mar 13, 2019 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
    Commented Mar 13, 2019 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
    Commented Mar 13, 2019 at 9:50
  • 1
    $\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. ♦
    Commented Mar 13, 2019 at 17:35
  • 1
    $\begingroup$ @kate You should remove that edit and create a second question. (The SE model typically involves only one question per question page) When I saw that you edited this one, I hoped that you had added in answers to some of the follow-up questions I had. I'm still not sure how to advise you without more information. $\endgroup$
    – Ben I. ♦
    Commented Apr 12, 2019 at 13:48

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your reply. Yes, computability itself is quite big, and my department is combining it with Complexity... those are two big subjects combined into one. Yes, I have the Michael Sipser book, it's very good. Perhaps I should integrate that one into the course if I managed to; currently mine is based on Peter Linz's book and Levitin's algorithm book. I thought JFLAP only does simple simulations of FA, but maybe I'm wrong; I'll try to study it better. $\endgroup$
    – kate
    Commented Apr 12, 2019 at 6:29
  • $\begingroup$ I wonder how other professors/TAs managed to give programming assignments to their students, such as building a CYK algorithm-based parser, but they provided the parser/compiler/backbone (?) $\endgroup$
    – kate
    Commented Apr 12, 2019 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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