Computer Science 456/656
Automata and Formal Languages
Spring 2006
Assignments

Revised May 9, 2006

Tuesday, January 17, 2006

Today we will broadly discuss the course as a whole.

We will introduce the basic concepts of symbol, alphabet string, and language.

Thursday, January 19, 2006

Today we will informally define the concepts of machine and computation and introduce the concept of a regular language.

More formal definitions of machine and computation will come later.

Tuesday, January 24, 2006

Today we will define regular expressions, and the equivalence of the three definitions of regular language.

We will learn how to minimize a DFA, and how to construct a DFA equivalent to a given NFA.

Thursday, January 26, 2006

We didn't get through all the topics from last time, so I will finish them today.

Tuesday, January 31, 2006

Turn in Assignment 1 at the beginning of class today.

We will spend a few minutes discussing some of the problems in Assignment 1.

We will summarize the closure properties of the class of regular languages, including union, intersection, concatenation, Kleene closure, complementation, inversion, and homomorphism.

If time permits, we will then discuss the fact that many languages which are of practical importance are not regular, including most algebraic languages and programming languages. The pumping lemma, which you are expected to understand, can be used to prove that these languages are not regular.

Thursday, February 2, 2006

Today, we will begin our discussion on context-free languages and push-down automata.

Tuesday, February 7, 2006

We will continue our discussion of context-free languages and grammars.

We will give some simple examples of context-free grammars which generate familiar languages.

We will list the standard closure properties of the class CFL. These include:

• Union
• Concatenation
• Kleene Closure
• Inversion

Is CFL closed under the following operations?

• Intersection
• Complementation
• Homomorphism

Other topics to be discussed (today or later) include Chomsky and Greibach normal forms, the CYK algorithm, and the pumping lemma for CFL. (This is different from the pumping lemma for regular languages.)

Thursday, February 9, 2006

Tuesday, February 14, 2006

Turn in Assignment 2 at the beginning of class today.

Thursday, February 16, 2006

Today, we will discuss the CYK algorithm for the membership problem for context-free languages. This is a dynamic programming algorithm.

Tuesday, February 21, 2006

First Examination today. Study guide.

(There will be a second mid-term examination later.)

Thursday, February 23, 2006

Today we will show two methods by which any CFL is accepted by a PDA. These two methods are both non-deterministic, but give us the models we need to understand deterministic parsers.

Tuesday, February 28, 2006

Today we will introduce deterministic parsing.

Thursday, March 2, 2006

Today we will continue our discussion of parsing.

Tuesday, March 7, 2006

Today, we will introduce the main part of the course, leading up to the proof, some days later, that some languages are undecidable, or equivalently, that there are true statements which have no proof. We will start by defining Turing machines.

Thursday, March 9, 2006 The major theme today is the Church Turing thesis. Any computation that can be done on any abstract machine of any type whatsoever can be done by a Turing machine. But it is necessary to have a clear understanding of what a "machine" (i.e., abstract machine) is. For example, it does not mean "physical machine." There can be no mathematical definition of "physical machine."
I think the reference to Peter Shor in the Wikipedia article is misleading. When I asked Peter whether any quantum machine could be emulated by a (usual) machine, he refused to answer for several minutes. After I really insisted, he seemed to say that the answer was yes. But I really need to pin this down.
I personally believe that no physical machine can compute anything that no Turing machine can compute. But here is a more cautious formulation.

Tuesday, March 21, 2006

Today we will begin the main thrust of the course: the proof that there are undecidable languages, i.e., undecidable decision problems.

We will spend some time showing how a decision problem (example: "Is this graph connected?") can be reformulated as a language, and vice versa.

The next order of business is to have a clear understanding of the meaning of "undecidable."

Undecidability is usually proved using reduction or diagonalization.

Thursday, March 23, 2006

Today we will prove that the halting problem is undecidable.

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.)

Tuesday, March 28, 2006

Today we will review undecidability.

Turn in Assignment 3 at the beginning of class today.

Thursday, March 30, 2006

Today we will introduce unrestricted grammars.

Tuesday, April 4, 2006

We will introduce the concept of complexity class.

If time permits, we will review some material that will be on Thursday's exam.

Thursday, April 6, 2006 Second Examination today. Study guide.

Tuesday, April 11, 2006

We will go over the exam.

Today, we will introduce the subject of {\em polynomial time complexity\/}.

Thursday, April 13, 2006

Today, we will continue our discussion of time complexity, and give the formal definition of NP-completeness.

Tuesday, April 18, 2006

Today, I will outline the proof that L_sat is NP-complete. The proof is rather involved and filled with confusing detail, but these details are not the essence of the proof. I will try to give an intuitively straightforward summary.

By reducing L_sat to L_3-CNF-sat in polynomial time, we show that L_3-CNF-sat is NP-complete.

By reducing L_3-CNF-sat to the independent set problem in polynomial time, we show that the independent set problem is NP-complete.

By reducing the independent set problem to the clique problem in polynomial time, we show that the clique problem is NP-complete.

Thursday, April 20, 2006

Here are some answers to some of the questions that were raised in class about NP-completeness, co-NP-completeness, and prime factorization.

Tuesday, April 25, 2006

With the rapid onset of parallel computers, the issue of efficient parallelization of existing sequential algorithms grows in practical importance. Can every sequential algorithm be parallelized with only a "small" loss of efficiency?

"Nick's Class" is the class of all problems that can be solved in polylogarithmic time with polynomially many processors. Trivially, NC is a subclass of P, but the question of whether NC = P is open, and its importance rivals that of the P = NP question. P-completeness is defined in a manner analogous to NP-completeness. If any one P-complete problem is in NC, then P = NC. Nick, himself!

Thursday, April 27, 2006

Parallel CYK?

Tuesday, May 2, 2006

Some problems on regular languages.

Sample LALR problems.

Sample problems about 3-CNF-SAT.

Sample problems about Turing machines.

The relationship among NC, P, NP, recursive, and RE explained.

Prove that the language consisting of all binary strings with an even number of 1's is in NC. Solution.

Thursday, May 4, 2006

What does this Turing machine do?

Tuesday, May 9, 2006 Office hours 7:20-10:00 today.

Tuesday, May 10, 2006 Office hours 9:00-11:30 today.

Tuesday, May 9, 2006 Office hours 7:20-10:00 today.

Tuesday, May 10, 2006 Office hours 8:20-11:30 today.

Thursday, May 11, 2006

Final Examination: 10:10 -- 12:10

I have decided I will definitely ask a question that looks like one of these.

Final Examination.

Practice final in postscript form.

Practice final in pdf form.

Monday, May 16, 2006

Monday, May 20, 2006