Computer Science 456/656
Automata and Formal Languages
Spring 2009
Assignments and Lecture Topics

Revised April 30, 2009

Tuesday, January 13, 2009

Today we will overview the course. The two most important key words of the course are language and computable. We will start by discussing languages.

English, Spanish, Chinese, and other natural languages, are not part of this course. Programming languages are, however.

Thursday, January 15, 2009

Today we will discuss the operations of union, concatenation, and Kleene closure on languages. The class of regular languages is closed under those three operations.

We will introduce regular expressions and non-deterministic finite automata (NFAs).

We state the Equivalence Theorem of Kleene, Rabin, and Scott.

Tuesday, January 20, 2009

We will give formal definitions of DFA and NFA today.

Today we will get started in proving the Equivalence Theorem. We will show how to construct a DFA equivalent to a given NFA. An NFA with n states is equivalent to a DFA with 2ⁿ states, although that number can usually be reduced by minimization.

Thursday, January 22, 2009

Turn in Assignment 1 at the beginning of class today.

Tuesday, January 27, 2009

Today we will discuss the pumping lemma.

If time permits, we will start discussing context-free languages.

Thursday, January 29, 2009

Turn in Assignment 2 at the beginning of class today.

Tuesday, February 3, 2009

Today we will discuss parsing.

Thursday, February 5, 2009

You will be held responsible for the content of today's lecture on reduction.

Tuesday, February 10, 2009

Turn in Assignment 3 at the beginning of class today.

Thursday, February 12, 2009

Examination today.

First exam, Fall 2007: in postscript form pdf form

First exam, Fall 2008: in postscript form pdf form

Please do not hesitate to send me email if you have a question about the material on the exam.

Tuesday, February 17, 2009

Our new GA is Akshat Pampanwar.

Thank you, Mr. Pampanwar, for stepping into this job with such short notice.

Thursday, February 19, 2009

Tuesday, February 24, 2009

Turn in Assignment 4 at the beginning of class today.

Thursday, February 26, 2009

Today we will begin the discussion of undecidability.

Tuesday, March 3, 2009

Today, I will introduce the pumping lemma for context-free languages, and compare it to the pumping lemma for regular languages.

I will give the complete proof that the halting problem is undecidable. This is by far the most important single thing you need to learn in the course, so I will repeat this proof at least two more times before the end of the semester.
In preparation for this lecture, it would be helpful to read about binary encoding of Turing machines.
Also, to get into the right mood for the diagonization proof of the undecidability of the halting problem, read about the Guardian of the Bridge who was "… doomed to guard this bridge until truth and lies are one." (Thanks to Emily Rodda.)

Thursday, March 5, 2009

Today, we will get into the "nitty-gritty" of Turing machines. We will show various Turing machines that compute simple functions, such as reversing a string or incementing a binary numeral.

If time permits, I will introduce the concept of an enumerator.
When I was young, I learned that "enumerable" means "countable," and that every subset of an enumerable set is enumerable.
That's true. But can you actually find the enumeration?
Suppose I ask you to list all the positive integers in order. Can you do it? Well, you might complain that it would take forever, but you could certainly design a machine that would do it. The machine would run forever, of course, but it would correctly print all the positive integers, and in canonical order. (Well, really, it would print the numerals for the positive integers.)
But what if you wanted to enumerate some subset of the positive integers? For example, the odd numbers? No problem. The prime numbers? Of course, you could do it, but your machine would be a bit more complex. Some other set of positive integers? Why not?

Tuesday, March 10, 2009

Today we will continue to discuss enumerators.

We will then consider the membership and equivalence problems for context-free grammars.

If time permits we will consider context-sentsitive and general grammars.

Thursday, March 12, 2009

Turn in Assignment 5 at the beginning of class today.

Tuesday, March 17, 2009

I will go over the proof that the halting problem is undecidable. This will be a beginning-to-end lecture, and is thus a repetition of the first lecture I gave on the subject.

I will repeat my introduction to the polynomial time and non-deterministic polynomial time classes. It is my experience that no amount of repitition of these concepts is too much.

In particular, I will talk about certificates.

Thursday, March 26, 2009

Examination today.

Tuesday, April 21, 2009

Today I will prove that 3-satisfiability is NP-complete.

If there is enough time, I will redo the proof that the halting problem is undecidable.

If there is time remaining, I will redo the proofs of both pumping lemmas.

Thursday, April 23, 2009 Turn in Assignment 6 at the beginning of class today.

Today, we will start reviewing the semester's material. We will emphasize the most important material for each of the major topics.

Tuesday, April 28, 2009

We will continue reviewing the semester's material. Today's review topic will be context-free grammars and languages.

Thursday, April 30, 2009

Today, we continue reviewing the semester's material.

Tuesday, May 5, 2009

Final Examination, 3:10 to 5:10.

Practice final in postscript form.

Practice final in pdf form.