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

Revised May 16, 2005

Tuesday, January 18, 2005

Today we will broadly discuss the course as a whole.

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

Discussion question of the day: What is the most important thing you will learn in this course?

Thursday, January 20, 2005

Today we will give a formal definition of a finite state machine, and what it means to say that a given machine accepts a given language.

Tuesday, January 25, 2005

Today we will continue our discussion of regular languages, regular expressions, and finite automata.

Thursday, January 27, 2005

Today we will continue our discussion of regular languages, regular expressions, and finite automata.

In particular, over the next several lectures, I will show how to minimize a DFA, and how to find a DFA which accepts the language described by a given regular expression, how to find an NFA equivalent to a given DFA, and how to construct a regular expression for the language accepted by a given NFA.

Here are some things to remember in case they come up in the "True/False" portion of the next examination: There is a unique minimal DFA for a given regular language, but there may be no unique minimal NFA, and there may be no unique minimal regular expression.

Tuesday, February 1, 2005

We will try to finish our discussion of regular languages today.

Thursday, February 3, 2005

Turn in Assignment 1 at the beginning of class today.

Today we will introduce the concept of context-free languages.

Tuesday, February 8, 2005

Today we will continue our discussion of context-free languages.

One of the problems in Assignment 2 can be worked very easily using the pumping lemma for regular languages, so I will introduce that today.

If time permits, we may finish some additional remaining topics on regular languages.

Thursday, February 10, 2005

Tuesday, February 15, 2005

Thursday, February 17, 2005

Today we will talk about parsers that are used in practice: in particular, top-down parsers and bottom-up parsers.

Tuesday, February 22, 2005

Today will continue our discussion of parsers and context-free languages.

Happy birthday to Ruth Anne Larmore, and also George Washington.

Thursday, February 24, 2005

Today I will state the pumping lemma for context-free languages, and use it to prove that { aⁿ bⁿ cⁿ } is not context free.

I will also prove both pumping lemmas, the one for regular languages and the one for context-free languages.

Tuesday, March 1, 2005

Turn in Assignment 3 at the beginning of class today.

I will finish the proofs of both pumping lemmas today.

Thursday, March 3, 2005

Examination today. Study guide.

Tuesday, March 8, 2005

Today we will begin the formal dicussion of Turing Machines and undecidability. This theme will last for several lectures.

Today's question: what does it mean for a problem to be undecidable?

Thursday, March 10, 2005

Turn in Assignment 4 at the beginning of class today.

Hopefully, I will turn back the graded exams today. I was unable to get them over the weekend to grade, which is a shame; otherwise I'd've had them for you Tuesday. (To you non-native speakers: I bet you didn't even know that "I'd've" is a perfectly correct word in informal spoken English!)

If time permits, we will continue the dicussion of Turing Machines and undecidability.

Today's question: what is the Church-Turing Thesis, and why is it important?

Tuesday, March 15, 2005

Turn in Assignment 5 at the beginning of class today.

Here is a quote from a famous mathematician:
"Words differently arranged have a different meaning and meanings differently arranged have a different effect."
Pascal, Blaise (1623-1662)
W. H. Auden and L. Kronenberger (eds.) The Viking Book of Aphorisms, New York: Viking Press, 1966.
Thanks to my student Dean Bartkiw, who pointed me to a page of quotations from famous mathematicians on the web.

The CYK algorithm is explained here.

Thursday, March 17, 2005

In each case where I had not figured it out, the grammar given by the student for problem 4(a) on the exam was ambiguous, so no additional points will be given to those six students.
I already told you that the problem of determining whether an answer was right was undecidable. But there's more to say about that. The set of all correct answers, just like the diagonal language, is not Turing acceptable.
But, the set of all incorrect answers, just like the complement of the diagonal langauge, is Turing acceptable. In fact, anyone qualified to take this course could easily (well, maybe in a couple of days, including debugging) write a program that, given an incorrect answer to the problem would halt and tell you that, and even have output explaining why (either it doesn't generate a string in L, or it generates it in two different ways), and given a correct answer to the problem, would run forever. (But, for any given n, after a finite amount of time, it would say that it was good for all strings in L of length up to n.)

Tuesday, March 29, 2005

We will continue to discuss Turing machines and computability. Today, I will convince you that any machine can be emulated by a Turing Machine machine, in order to justify the Church-Turing thesis.

Today, if there's time, we'll begin the discussion of polynomial complexity. This leads to the extremely important issue of whether certain problems can be solved in a reasonable amount of time or space.

Thursday, March 31, 2005

Tuesday, April 5, 2005

Thursday, April 7, 2005

Tuesday, April 12, 2005

Examination today in class. Study guide.

Wednesday, April 13, 2005

The examination is graded. The median score is 89 out of 150.

Thursday, April 14, 2005

Today I will hand back the examination and discuss the problems.

We will then begin a needed review of some concepts I introduced a while back, starting with the diagonal language and undecidability.

If there is time, I will introduce general grammars.

Tuesday, April 19, 2005

Today we will try to prove two theorems:

• Boolean satisfiability is NP-complete.
• Boolean 3-cnf-sat is NP-complete.

The second theorem is proved by reduction, using the first theorem, so I should prove the first theorem first. But I'll do them in reverse order; since the second theorem is easier.

Thursday, April 21, 2005

Turn in Assignment 6 at the beginning of class today.

Today, we will complete the proof the boolean satisfiability is NP-complete.

Tuesday, April 26, 2005

Today we will discuss deterministic parsers that are used in practice. I will concentrate on a standard kind of parser called an LALR parser.
In order for a parser to be of practical use, it must

1. be deterministic,
2. be fast,
3. have finite lookahead,
4. be able to parse the underlying context-free grammar of a modern programming language.

Here is an LALR parser. The third page contains a table without entries for an LALR parser for a different grammar. This other grammar is ambiguous, containing the "dangling else" problem, but the LALR parser, if properly designed, will unambiguously parse any string by resolving the "else" problem in the proper way.
Here is the PDF version.

A refresher on the relationship between "languages" and "problems."

and NP-completeness.

L_3-cnf-sat is NP-complete.

Certificates.

Thursday, April 28, 2005

Today I will review what we did on Tuesday, but from a simpler point of view.

Here are some test strings that are generated by the second grammar in the handout, the one we went over in class today. If you work through all of these, you should be able to fill in most of the entries in the action and goto tables.
In the action table, there is at most one reduction in any row, and there is at most one shift in any column. This rule does not hold in general, but there will be very few exceptions in most practical situations. One deviation from this rule is caused by the use of the minus sign to represent both subtraction and the unary operator negation.

I will put up the answer, i.e., the filled in action and goto tables, on Monday.

Tuesday, May 3, 2005

In many cases, an LALR parser can handle an ambiguous grammar unambiguously, making all the right choices.
For example, this grammar is highly ambiguous, yet you can easily design an LALR parser that always finds the desired parse tree, i.e., one the respects the normal precedence of operators.

An example of the use of the CYK algorithm:
postscript
pdf

Thursday, May 5, 2005

Today we will review the material that will be on the final exam.

Practice final in postscript format and in pdf format. I will be making minor additions or changes today and perhaps tomorrow.

Some people (including me) were unable to access faculty web pages (including this one) for the last 3 days from home. Because this problem was not visible from the Engineering building, the systems administrators thought they had solved it until I alerted them. Now, as of about 6 pm Thursday, it appears to be fixed. If anything like this should recur, send me email.

Thursday, May 12, 2005

Final Examination at 10:10 AM.

challenge problems are absolutely due at 10:10 AM today.

Monday, May 16, 2005

Course grades have been assigned.