Required Reading

CSE396 Course Information, Spring 2026

Instructor:

Dr. Kenneth W. Regan, 326 Davis Hall, 645-4738, regan@buffalo.edu

TA:

Sean Grzenda, seangrze@buffalo.edu

(other staff TBA)

Office Hours: (tentative)

• Regan: Wednesdays 1--3pm, Thursdays 3:30--5pm
• Grzenda, TBA.

Lectures and Recitations:

(LEC)

TuTh 5:00--6:20pm in Hochstetter 114

(R2)

Th 9:30AM - 10:20AM in Clemens 204

(R3)

Fr 10:00AM - 10:50AM in Capen 108

(R4)

Fr 9:00AM - 9:50AM in Capen 108

Recitations do not meet in Week 1.

Syllabus. Tentative, some matters subject to change.

Syllabus from 2019

Examinations:

• Two prelims, the first on Thursday, March 5, in class period. The second will be in late April.
• One cumulative 3-hr. final.

Spring 2026 Assignments

(will be accumulated here; see below for 2021 assignments)

Lecture Notes

1. Week 1: Thu.
2. Week 2: Tue. Thu. And recitations.

Piazza page for Spring 2026

TopHat page for Spring 2026

Lecture Notes in 2021

(will be largely followed in 2026, but note Tue.-Thu. "stagger"!)

1. Week 1: Tue. Thu. (part before demo)
2. Week 2: Tue. Thu.
3. Week 3: Tue. Thu.
4. Week 4: Tue. Thu.
5. Week 5: Tue. Thu.
6. Week 6: Tue. Thu.
7. Week 7: (Tue=Prelim I) Thu.
8. Week 8: Tue. Thu.
9. Week 9: Tue. Thu.
10. Week 10: Tue. Thu.
11. Week 11: Tue. Thu.
12. Week 12: Thu. (Tue. was Prelim II)
13. Week 13: Tue. Thu. (plus first half of Tue. 5/4)
14. Week 14: Tue. Thu.

Required Reading

1. Textbook: Michael Sipser, Introduction to the Theory of Computation, 3rd Edition. See the end of the syllabus PDF for intended coverage by-chapter.
2. Handouts posted by the instructor, chosen from options itemized below.

Extra Resources (some may be used officially)

• Setup instructions for the "Turing Kit" DFA/TM simulator (optional).

  Or more simply, download TKIT70.zip to your PC, unzip and navigate your command line to that folder, and run

  java -cp TKIT70.jar Main

  Open the file DragonSL.tmt and then do View--Auto Resize to get a bigger canvas. You can also load a different color scheme and much else.
  
  

• Scribe notes (original smaller-font version) by Arun Debray from lectures by Ryan Williams using Sipser's textbook.

• Alternative, majorly different textbook by Boaz Barak, whose draft is freely available online and was used in Spring 2025. However, it requires a major roadmap to approach; e.g., chapter 1 of Sipser's text picks up in the middle of chapter 6 there.

• ASCII text pseudocode for the FA-to-regexp algorithm, expressed using a matrix of regular expressions.

• Supplementary lecture notes on the Myhill-Nerode Theorem. Note too that this is covered in the Chapter 1 problems section, and latest editions of Sipser give the proof (both directions) in the answers section.

• Typeset and expanded handout on "Structural Induction" using context-free grammars.

• Supplementary handout on Chomsky normal form conversion, with a worked-out example. (This spells things out more than the text does in its proof of Theorem 2.9---adding two optional steps removing "dead" and "unreachable" variables---but it's the same process.)

Notes on Turing Machines and PDAs (some sideways):

• Collatz 3n+1 Problem
• Balanced Parentheses PDA
• Two-Tape TMs
• Two-tape TM for {ww: w \in {0,1}*}.
• Universal RAM Simulator sketch.

Spring 2021 Assignments

(their answers will be available inside Piazza)

1. Assignment 1, due Tue. 2/16, 11:59pm
2. Assignment 2, due Tue. 2/23, 11:59pm
3. Assignment 3, due Tue. 3/2, 11:59pm
4. Assignment 4, due Tue. 3/9, 11:59pm
5. Assignment 5, due Tue. 3/23, 11:59pm
6. Assignment 6, due Tue. 3/30, 11:59pm
7. Assignment 7, due Tue. 4/6, 11:59pm
8. Assignment 8, due Tue. 4/13, 11:59pm
9. Assignment 9, due Tue. 4/27, 11:59pm
10. Assignment 10, due Thu. 5/6, 11:59pm

Nature and Purposes of the Course

The first main objective of the course is to convey those major concepts and results in the theory of computation that guide our thinking about the power of computers and the problems we can solve with them. This includes the entire historical origin of the field in the work of Alan M. Turing, John von Neumann, and Stephen C. Kleene. Finite automata, regular expressions, context-free (and other) grammars, pushdown automata, and idealized programs (if not the Turing machine, think of the Java Virtual Machine) are tools of everyday computing practice. Computational complexity theory asks the fundamental question of how much time, memory, and other computational resources computers need to solve certain problems, and today is relied upon for Internet security.

A second main objective is not as "concrete" as the above-listed syllabus material, but is just as important. Computers are by-nature entirely formal entities---they do precisely what is prescribed in programming languages that are ultimately formal and mathematical. Not just to reason about them, but even to communicate effectively in the field and on the job, one must be able to state assertions precisely and design prototypes concisely. This requires fluency in the underlying mathematical language used to describe problems, computations, and objectives. This course gives valuable training in formal modes of reasoning, analysis, and presentation.

Items From Previous Semesters

Sample Prelim I Exam, from Spring 2019

Sample Prelim II Exam, from Spring 2019

Sample Final Exam, from Spring 2019

Lecture Notes in 2019

• Week 1: Tue. (Thu. in-class demo)
• Week 2: Tue. Thu.
• Week 3: Tue. Thu.
• Week 4: Tue. Thu.
• Week 5: Tue. Thu.
• Week 6: Tue. Thu.
• Week 7: Tue. was Prelim I. Thu. of that week was a weird happening---see week 7 lectures from 2018.
• Week 8: Tue. Thu.
• Week 9: Tue. Thu.
• Week 10: Tue. Thu.
• Week 11: Tue. Thu.
• Week 12: Tue. Thu. is Prelim II
• Week 13: Tue. Thu.
• Week 14: Tue. Thu.

Lecture Notes from 2018

• Week 1: Tue. Thu.
• Week 2: Tue. Thu.
• Week 3: Tue. Thu.
• Week 4: Tue. Thu.
• Week 5: Tue. Thu.
• Week 6: Tue. Thu.
• Week 7: Tue: Prelim I Thu.
• Week 8: Tue. Thu.
• Week 9: Tue. Thu.
• Week 10: Tue. Thu.
• Week 11: Tue. Thu.
• Week 12: Tue. (Thu. = Prelim II)
• Week 13: Tue. Thu.
• Week 14: Tue. Thu.

Lecture Notes from 2017

• Week 1: Tue. Thu.
• Week 2: Tue. Thu.
  Week 2 recitation notes are here; those for Week 3 are pages 4 & 5 of the Thu. 2/9 notes.
• Week 3: Tue. Thu.
• Week 4: Tue. Thu.
• Week 5: Tue. Thu,
• Week 6: Tue. Thu.
• Week 7: Exam but no lecture owing to snow closure.
• Week 8: Tue. Thu.
• Week 9: Tue. Thu.
• Week 10: Tue. Thu.
• Week 11: Tue: TM/PDA notes linked above. Thu.
• Week 12: Tue. (Thu. = Prelim II)
• Week 13: Tue. Thu.
• Week 14: Tue. Thu.
• Review Session Notes

Spring 2016 Lecture Notes

• Week 1: Tue. Thu.
• Week 2: Tue. Thu.
• Week 3: Tue. Thu.
• Week 4: Tue. Thu.
• Week 5: Tue. Thu.
• Week 6: Tue. Thu.
• Week 7 (one lecture): Thu.
• Week 8: Tue. Thu.
• Week 9: Tue. Thu.
• Week 10: Tue. Thu.
• Week 11: Tue. Thu.
• Week 12 (one lecture): Thu.
• Week 13: Tue. Thu.
• Week 14: Tue. Thu.
• Also notes from the 5/9 Review Session