CSCI 341 Theory of Computation

Fall 2025, with Schmid

Table of Contents

References

These course notes did not come from nowhere! Section 1 is largely based on Todd's notes on automata theory, except for the puzzles and games in those subsections. Section 2 is very standard material, based on the textbook of Sipser and the classic textbook of Hopcroft, Motswani, and Ullman. The \(\lambda\)-calculus subsection is directly based on a set of notes from a course taught by Peter Selinger at Dalhousie.

Source Material

All of the writing in these notes and the in the references for the course lecture structure given above should be considered secondary sources. They aren't the original papers where the ideas behind the concepts were introduced. Below is a list of the original source material for each topic.

• First appearance of regular expressions: Stephen Cole Kleene, "Representation of Events in Nerve Nets and Finite Automata", 1951
• Brzozowski introducing his notion of derivative: Janusz A. Brzozowski, "Derivatives of regular expressions", 1964
• Antimirov introducing his notion of derivative: Valentin Antimirov, "Partial derivatives of regular expressions and finite automaton constructions", 1996
• Arden's Rule: Dean N. Arden, "Delayed Logic and Finite State Machines", 1961
• First appearance of the pumping lemmas (see Lemma 8, for eg.)? There seems to be some uncertainty about when these were first proven: Dean N. Arden, "Delayed Logic and Finite State Machines", 1961
• First appearance of context-free grammars: Noam Chomsky, "Finite Automata and Their Decision Problems", 1959
• Context-free languages and their equivalence with stack (i.e., pushdown) automata: M.O. Rabin and Dana Scott, "On context-free languages and push-down automata", 1963
• The first careful development of the \(\lambda\)-calculus: Alonzo Church, "An unsolvable problem of elementary number theory", 1936