Instructor:
Dr. Kenneth W. Regan, 326 Davis Hall, 645-4738, regan@buffalo.edu
TA:
Rui Li, rli35@buffalo.edu
Office Hours:
Syllabus from 2019 (differences to be noted in first lecture but mostly similar)
Survey Sheet (non-graded item on Autograder)
Sample Prelim II Exam, from Spring 2019
Sample Final Exam, from Spring 2019
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.
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 both 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):
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.