Instructor:
Dr. Kenneth W. Regan, 218 Bell Hall, 645-4738, regan@buffalo.edu
TAs:
Robert Surowka, robertlu@buffalo.edu Jiun-jie Wang, jiunjiew@buffalo.edu
Office Hours:
Setup instructions for the "Turing Kit" DFA/TM simulator.
Week 2-or-3 recitation notes: page 1, page 2, page 3.
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 the 2nd.\ ed.\ of Sipser gives the proof (both directions) in its answers section.
Scans of handwritten handout on induction proofs and context-free grammars, featuring "Structural Induction": page 1, page 2.
Supplementary handout on Chomsky normal form conversion, with a worked-out example. (This is from the mid-1990s with Martin's text---the notation is different from lecture but the process is the same.)
Assignment 10, due Wed. 4/21 in class.
Assignment 11, due Mon. 4/26 in class.
Scan of handwritten answer key to Assignment 3: page 1, page 2.
Scan of key to problems (1)--(3) of Assignment 4: here.
Problem Set 5 answer key: plaintext file.
Problem Set 6 answer key: plaintext file.
Problem Set 7 answer key: plaintext file.
Problem Set 8 answer key: plaintext file.
Problem Set 9 answer key: plaintext file and TM drawing for part 4(a).
Problem Set 10 answer key (regular-credit portion only): plaintext file.
Problem Set 11 answer key plaintext file.
Sample Prelim II's from a previous year---as annotated on the
hardcopy given out on Wed. 4/7, your exam will be "like" a combination
of the first with problems (1) and (3) of the "makeup" version, and
unlike these, your exam will be open book, open notes.
page 1,
page 2 (that year's makeup version).
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.