Computer Science 456/656
Automata and Formal Languages
Fall 2004
Assignments

Revised December 20, 2004

Background.

It is important to have a fundamental understanding of logic and the language of proofs, as well as basic (grade school) understanding of set theory.

There is substantial amount of background material in Chapter 0 of your textbook, although that chapter also contains material that I do not expect you to know already, such as the definition of an automaton.

Tuesday August 31, 2004.

Today we will broadly discuss the course as a whole.

We will then introduce the basic concepts of symbol, alphabet, and language, followed if time permits, by the concepts of finite state machine and regular language.

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

Thursday September 2, 2004.

Today we will learn about finite automata and regular languages, Section 1.1 in your textbook.

Tuesday September 7, 2004.

Today we will learn about non-deterministic finite automata. The abbreviation is NFA.

Thursday September 9, 2004.

Turn in Assignment 1 at the beginning of class today. Note addition of problem 1.4 to the assignment.

Today I will give two algorithms I promised you:

• Given an NFA, construct an equivalent DFA.
• Given a DFA, construct an equivalent minimal DFA.

It is important to note that every DFA is an NFA, but not vice-versa.

Tuesday September 14, 2004.

Today we will concentrate on regular expressions and the theorem that a language is regular if and only if it is described by a regular expression.

We shall give a technique for analyzing the regularity of languages. Suppose L is a language over an alphabet Sigma. If u and v are strings, we say that u and v are L-equivalent if, for any string w over Sigma, uw is in L if and only if vw is in L. Theorem: If L is regular, there are finitely many L-equivalence classes, and the number is equal to the number of states of the minimal DFA that accepts L. Furthermore, if L is not regular, there are infinitely many L-equivalence classes.

Thursday September 16, 2004.

Today we will give an introduction to context-free grammars.

Warning: just as the tunnel was closed at times during President Bush's visit on Tuesday, the tunnel will probably be closed at times during Senator Kerry's visit today. (He is speaking to the same group that Bush spoke to on Tuesday.) I would recommend staying far away from the airport and the road from the airport to the convention center. (In the 2000 election, these closures sometimes happened without warning, causing it to take me hours to get home one evening after class. At least, now, we are warned.)

Tuesday September 21, 2004.

Examination today. The exam will cover all material up until this point in the course. Study Guide.

Thursday September 23, 2004.

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

Tuesday September 28, 2004.

Due to medical emergency, there will be no office hour today.

I plan to hand back the graded exam today.

Today we will do the pumping lemma.

Thursday September 30, 2004.

Today I will introduce the pumping lemma for context-free languages, and show how its proof parallels that of the pumping lemma for regular languages.

If time permits, I will dicuss PDAs and parsers.

Let me remind everybody that, when you send me email, you must write CS456 or CSC656 as the first thing in the subject field. (You can write other things after that in the subject field if you wish.) The reason is that the level of spam is so bad that I am forced to erase most messages without reading them.

Due to continuing medical situation, I will cancel my 7pm office hour tonight.

Tuesday October 5, 2004.

Today we will discuss the relation between syntax and semantics.

Thursday October 7, 2004.

Today We will discuss PDAs and context-free languages.

Turn in Assignment 2 at the beginning of class today.

Tuesday October 12, 2004.

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

Thursday October 14, 2004.

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

We will introduce the concept of an ambiguous grammar.

Tuesday October 19, 2004. Today we will continue our discussion of context-free languages.

Most languages that are used in practice have a semantics (a fancy word for meaning). We will introduce the concept of a context-free grammar that is not only unambiguous, but also respects the semantics of the language.

Thursday October 21, 2004.

Turn in Assignment 3 at the beginning of class today.

Study guide for the examination for next Thursday.

Tuesday October 26, 2004.

Turn in Assignment 4 at the beginning of class today.

We will begin our discussion of the main part of the course, the theory of computability.

Thursday October 28, 2004.

Examination today. The exam will cover all material up until this point in the course.

Tuesday November 2, 2004.

Return Examination today.

We will continue our discussion of enumerability by machine.

Thursday November 4, 2004.

We will continue our discussion of enumeration. An illurstration of an enumerator (using one of the two definitions I gave in class) is in Figure 3.8 on page 140 of your textbook.

Tuesday November 9, 2004.

Today we will discuss the concept of decidability and also the concept of recursive enumerability.

One of the things we will prove is that the so-called halting problem is undeidable.

Thursday November 11, 2004. Veterans' Day holiday. Originating as a holiday honoring the dead of the Great War (now called the First World War), today we honor all those who have served in the Armed Forces.

Tuesday November 16, 2004.

Today we will repeat our discussion of undecidability. Therefore, if you were confused last week, you will understand it today.

Thursday November 18, 2004.

Turn in Assignment 5 at the beginning of class today.

Today we will introduce the concept of a polynomial function, and the related concept of a computation that runs in polynomial time.

It has come to my attention that some students think that "my door is not open" if the door to the B378 suite is closed. Nothing could be further from the truth. The door to B378, which leads to B378A, B378B (my office) etc., is always closed, and always unlocked. There used to be a way to hook it open, but the hook has been removed, possibly by the fire marshall. So just open it and go in.

Tuesday November 23, 2004.

We will go through a very slow, deliberate, definition to explain what it means for a language to be in the class NP.
To say that a language is accepted by a non-deterministic machine in a short time is akin to to an advertisement that said that you are only "six little numbers" away from becoming a millionaire by playing the lottery.

Thursday November 25, 2004.

Thanksgiving Day holiday.

Tuesday November 30, 2004.

Today I will outline the proof that the independent set problem is NP-complete. The proof is in three parts:

1. Prove that boolean satisfiability is NP-complete.
2. Prove that L_3-CNF-sat is NP-complete, by reducing boolean satisfiability to L_3-CNF-sat in polynomial time.
3. Prove that the independent set problem, the set of all strings of the form such that is the binary encoding of some graph that has an independent set of k vertices, is NP-complete. We do this by reducing L_3-CNF-sat to the independent set problem in polynomial time.

Thursday December 2, 2004.

We will continue the discussion of Tuesday.

Tuesday December 7, 2004.

Today we will finish up the discussion on NP-completeness, as much as possible.

Thursday December 9, 2004.

Reviews and summaries.

One of the students left his wallet in the classroom. If he doesn't pick it up from me tonight, I will turn it over to the computer science office for safekeeping.

Final Examination.

Study Guide. Our final examination is scheduled for 6:00 PM on Tuesday, December 14. The examination will be comprehensive.

Thursday December 16, 2004.

I have not yet prepared the final grades. If you want to know your final grade, send me an email message with "CS456" or "CSC656" in the subject line, and state your name and student ID number. Sending that email only once is sufficient.

Monday December 20, 2004.

The grades are now finished. I will send email tomorrow to all those who've requested.