Teaching next term

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.

  1. 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
  2. Finite automata
    • Section 1.1-1.2
    • DFAs
      • Concept
      • Definition
      • Examples (lots of them)
    • NFAs
      • Concept
      • Definition
      • Examples
  3. 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
  4. Regular expressions
    • Concepts
    • Inductive definition
    • Regexps -> NFAs
    • (sketch) NFA -> Regexps
    • Ask class to make a regular expression for balanced parentheses
  5. 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
  6. Context-free languages
    • Context free languages
    • Context free grammars
      • Examples of context free grammars
    • Chomsky Normal Form
      • Examples
    • Introduction of PDAs
      • Intuitive definition
      • Examples
  7. PDAs
    • Concept
    • Definition
    • Examples
    • (sketch) CFL pumping lemma
    • CFG -> PDA
    • (sketch) PDA -> CFG
  8. 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
  9. Turing machines II
    • Decidability
    • Recognizability
    • Decidable languages
    • Diagonalization proofs
  10. Recursion Theorem
    • This is the one I’m still thinking about the hardest
  11. 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
  12. Lambda calculi II
    • Church encodings
      • Booleans
      • Numbers
    • Control flow constructs
      • If-then-else
      • Recursion/Y-combinator
    • Writing simple programs

3 thoughts on “Teaching next term

      • 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:


        The draft book is also on the website.

        If you have more questions, just ask.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s