So just a small update today because I’m trying to work on this paper I want to put up on arXiv in the next month. I’m going to be teaching the undergraduate theory of computation course next term, based out of Sipser’s book since that’s what the graduate theory course almost always uses. I’ve TAed for this class before, and have TAed for the graduate version of it, but I haven’t actually ran an undergraduate class by myself before. It’s more intimidating than the category theory course I did a few years ago because, well, grades actually matter here and it’s not just a seminar that I can be very informal with. The following is my current plan for what I’ll cover in a *rough* plan of lectures. Now, I’ll have I believe 17 full two hour lectures to cover this material so I’m deliberately undershooting the number of lectures I’m planning because almost assuredly some of these will take 1.5 or 2 lectures to complete rather than just one. This is actually the outline I’ll be filling out here and there to try and plan out my lecture notes in advance and I think I’ll go ahead and post my lectures to the blog after I give them in class.

My goals are to cover all that basic material such as DFAs and PDAs since they’ll need to know it for the graduate course, but I want to save time to veer off into lambda calculi for a bit at the end. Turing machines are nice because they’re *manifestly* a computable process but, at least for me, there’s a conceptual discontinuity between computation as done by a Turing machine and how I see computation as done by programming languages. The lambda calculus comes into play, then, because it’s a simple programming language that we *know* is equivalent to a Turing machine. We can also show that you don’t *need* a lot of programming language features in order to have the full power of a Turing-equivalent computational model.

In any case, if anyone reads this and has any suggestions for particular topics and examples to cover please let me know! I’d love to hear from people with more experience teaching undergrad courses like this.

- Introduction
- Class Goals & Overview
- Big Picture Outline
- What is computation?
- Finite automata
- Pushdown automata
- Turing machines
- Decidability

- Lambda calculus

- Proof concepts
- Proof by construction
- Proof by contradiction

- Finite automata
- Section 1.1-1.2
- DFAs
- Concept
- Definition
- Examples (lots of them)

- NFAs
- Concept
- Definition
- Examples

- Equivalence of DFAs and NFAs
- Section 1.2
- Proof concept
- Proof by construction
- Examples
- Operations on DFAs and NFAs
- Section 1.2
- Operations on regular languages induce operations on automata
- Union, complement, intersection, Kleene star, concatenation
- Union/Intersection for DFAs
- Complement for DFAs
- Union for NFAs
- Why is intersection harder for NFAs?

- Concatenation for NFAs
- Kleene star for NFAs

- Regular expressions
- Concepts
- Inductive definition
- Regexps -> NFAs
- (sketch) NFA -> Regexps
- Ask class to make a regular expression for balanced parentheses

- Proving languages non-regular
- Pumping lemma
- Proof of lemma
- Examples of use
- Balanced parentheses
- Language of palindromes

- Myhill-Nerode
- Proof of theorem
- Use of theorem

- Pumping lemma
- Context-free languages
- Context free languages
- Context free grammars
- Examples of context free grammars

- Chomsky Normal Form
- Examples

- Introduction of PDAs
- Intuitive definition
- Examples

- PDAs
- Concept
- Definition
- Examples
- (sketch) CFL pumping lemma
- CFG -> PDA
- (sketch) PDA -> CFG

- Turing machines I
- Digression on Turing’s life and death
- Basic idea of a Turing machine
- Turing machines as models of human computation
- Formal Descriptions
- Examples
- Variants of Turing machines
- Multi-tape
- Non-deterministic
- How these are equivalent to plain ‘ol Turing Machines

- Turing machines II
- Decidability
- Recognizability
- Decidable languages
- Diagonalization proofs

- Recursion Theorem
- This is the one I’m still thinking about the hardest

- Lambda calculi I
- Tying computation to programming languages
- History of the lambda calculus
- Church-Turing thesis
- Inductive presentation of the untyped lambda calculus
- Evaluation rules

- Lambda calculi II
- Church encodings
- Booleans
- Numbers

- Control flow constructs
- If-then-else
- Recursion/Y-combinator

- Writing simple programs

- Church encodings

I thought I’d mention my Forlan formal language theory toolset and draft textbook on formal language theory: alleystoughton.us/forlan. You or your students might find it a useful supplement.

Hi Alley,

Can you give me a bit of a summary of what it does and how it’s used?

Forlan implements the many algorithms (closure properties, conversions, etc.) of formal language theory in Standard ML, so that one can write programs that manipulate regular expressions, five kinds of automata (including ones where transitions are labeled by strings and regular expressions), grammars and the functional programs I use instead of Turing machines — “programs below”. Everything has concrete syntax, but there is also a graphical editor for automata, regular expressions (as trees), parse trees and programs (as trees). Finite automata are giving meaning using labeled paths, and grammars using parse trees, and there are functions for searching for an accepting labeled path and for a parse of a string. There are algorithms for regular expression simplification. The programs mentioned above may be executed.

If you want to learn more, and see a cool extended example of what can be done with Forlan, look at my FDPE’08 paper:

http://doi.acm.org/10.1145/1411260.1411267

The draft book is also on the website.

If you have more questions, just ask.

Alley