<p>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. </p>

<p>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. </p>

<p>Automata and Computability is quite a lot on its own. </p>

<p>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? </p>

<p>But if you want to have a course that includes programming, you should at least look at <a href="http://www.jflap.org" rel="noreferrer">JFlap</a>, 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. </p>

<p>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:</p>

<p><a href="https://rads.stackoverflow.com/amzn/click/com/0632011769" rel="noreferrer" rel="nofollow noreferrer">A First Course in Formal Language Theory</a></p>

<p><a href="https://rads.stackoverflow.com/amzn/click/com/0632013079" rel="noreferrer" rel="nofollow noreferrer">A First Course in Computability</a></p>

<p>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. </p>

<p>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
<a href="https://rads.stackoverflow.com/amzn/click/com/113318779X" rel="noreferrer" rel="nofollow noreferrer">Introduction to the Theory of Computation</a> by Michael Sipser. I expect it would be clear and deep. </p>

CC BY-SA 4.0
2019-04-12T06:29:42.207Z
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.
kate
CC BY-SA 4.0
2019-04-12T06:31:18.753Z
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 (?)
kate
CC BY-SA 4.0
2019-03-13T10:35:38.813Z
2019-03-13T18:26:56.680Z
2019-03-13T18:26:56.680Z
Buffy
<p>i'm a new instructor &amp; also new here. </p>

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

<p>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? </p>

<p>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).</p>

<p>Thank you very much.</p>

<p>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 (?). </p>

CC BY-SA 4.0
2019-03-13T07:32:38.123Z
Hello, and welcome to [cseducators.se]. I hope you have found the site helpful so far. You have the needed reputation points to join [The Classroom](https://chat.stackexchange.com/rooms/59174/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.
Gypsy Spellweaver
CC BY-SA 4.0
2019-03-13T09:22:15.953Z
This question can probably be split into really good questions, which are a better fit for the Q&A system of this site.
ItamarG3
CC BY-SA 4.0
2019-03-13T09:50:54.537Z
Thank you for the comments and the chatroom. I'll edit again later if I manage to split the question down.
kate
CC BY-SA 4.0
2019-03-13T17:35:45.287Z
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?
Ben I.
CC BY-SA 4.0
2019-04-12T13:48:04.707Z
@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.
Ben I.
<lesson-ideas><student-motivation>
How do you teach Theory of Automata / Formal Language Theory / Computation Complexity?
# How do you teach Theory of Automata / Formal Language Theory / Computation Complexity?

(Asked by: username_0 on 2019-03-13)

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 (?).

**Tags:** lesson-ideas, student-motivation

> **Comments:**
> **username_1**: Hello, and welcome to [cseducators.se]. I hope you have found the site helpful so far. You have the needed reputation points to join [The Classroom](https://chat.stackexchange.com/rooms/59174/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.  
> **username_2**: This question can probably be split into really good questions, which are a better fit for the Q&A system of this site.  
> **username_0**: Thank you for the comments and the chatroom. I'll edit again later if I manage to split the question down.  
> **username_3**: 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?  
> **username_3**: @username_0 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.  

---

## 1 answers

### Answer by username_4 on 2019-03-13. Score: 5 | Accepted answer

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](http://www.jflap.org), 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](https://rads.stackoverflow.com/amzn/click/com/0632011769)

[A First Course in Computability](https://rads.stackoverflow.com/amzn/click/com/0632013079)

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](https://rads.stackoverflow.com/amzn/click/com/113318779X) by Michael Sipser. I expect it would be clear and deep.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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 (?)  

---

