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

Revised May 17, 2004

Tuesday, January 20, 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, January 22, 2004

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 27, 2004

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

Thursday, January 29, 2004

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

In particular, I will show how to minimize a DFA, and how to find an NFA which accepts the language described by a given regular expression.

Given an NFA, there is a regular expression for the language that it accepts. The proof of this fact is considerably harder than the proofs mentioned in the previous paragraph. If time permits, I will begin the discussion of that topic.

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.

Turn in Assignment 1 at the beginning of class today.

Tuesday, February 3, 2004

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

Thursday, February 5, 2004

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

Tuesday, February 10, 2004

Today we will continue our discussion of context-free languages, and finish any remaining topics on regular languages.

Doina will be taking the class today, and normal office hours in the morning are canceled.

Turn in Assignment 2 at the beginning of class today.

Thursday, February 12, 2004

I'm back, and will continue the discussion of context-free languages.

Tuesday, February 17, 2004

Thursday, February 19, 2004

First Examination today. Read the study guide.

I will be in my office most of the morning, starting at approximately 3:00 AM, but leaving by 5:00 AM, then back again before 8:30. Feel free to drop by or phone me.

Tuesday, February 24, 2004

Thursday, February 26, 2004

Today I will hand back the tests.

I will also prove the Pumping Lemma for regular languages.

Tuesday, March 2, 2004

Today I will finish the proof of the Pumping Lemma for regular languages. I only need another 5 or so minutes.

I will prove the Pumping Lemma for context-free languages. I will use (but not prove) Theorem 2.6 on page 99 of your textbook in the proof. That theorem just makes the proof of the Pumping Lemma a bit easier to understand (hint: using a CNF grammar, the parse tree of a string is effectively a binary tree) but I don't really need it, actually.

<"http://sigact.acm.org/sigactnews/quotes/">The quote about nested quantifiers. This is true, but Ian Parberry was much too nice to tell the full story.

Thursday, March 4, 2004

Today I will prove that every context-free language is accepted by some PDA. There are two separate proofs. One proof uses bottom-up parsing, and the other uses top-down parsing. Therefore, these proofs actually give you insight into how real-life parsers work.

Tuesday, March 9, 2004

Normal office hour in the morning is canceled today.

Turn in Assignment 3 at the beginning of class today.

The graduate assistant. will come today and go over problems, including the homework problems.

Thursday, March 11, 2004

Today we will begin the main subject of the course, namely undecidability. This issue and related issues will occupy most of the rest of the course. We will begin with an overview of the concept, and then introduce Turing machines.

Tuesday, March 16, 2004

Today we will begin the formal introduction to Turing Machines and the Church-Turing hypothesis.

Thursday, March 18, 2004

Tuesday, March 23, 2004

Second Examination today. Read the study guide, which is being updated over the weekend.

Summer 2003: First Examination (Uses the same textbook.)

Thursday, March 25, 2004

More discussion on Turing machines and computability.

I probably will not hand the test back today.

Tuesday, March 30, 2004

More discussion on Turing machines and computability.

I probably will not hand the test back today.

Thursday, April 1, 2004

I plan to hand the test back today. My office door will remain locked until 10am. Please do not knock until then unless it is truly an emergency that cannot wait until 10am.

I will also discussing on Turing machines and computability. The concept of enumerable and recursively enumerablewill be defined. They are not the same. Every language is enumerable, but not every language is recursively enumerable.

A set is enumerable if there exists a sequence consisting of every element of the set. But the existence of that sequence does not imply that there exists a machine that can find it.

Tuesday, April 13, 2004

Today I will talk about enumeration. Here is a paradox for you to contemplate, one that bothered me for years, but which I can use to introduce the issues of enumeration, recursive enumeration, and canonical recursive enumeration.

Thursday, April 15, 2004

I am in my office now, at Thu Apr 15 10:18:46 PDT 2004.

Today we will talk about reduction and hardness.

Tuesday, April 20, 2004

Turn in Assignment 4 at the beginning of class today.

Today I will begin the discussion of polynomial time complexity, leading up to a definition of NP-completeness.

Thursday, April 22, 2004

Today I will do some problems involving general grammars.

We will then continue our discussion of polynomial time complexity and NP-completeness.

Tuesday, April 27, 2004

Just a reminder: I now delete all email messages, without reading them, unless I know exactly who they are from. So, please use your real name and be sure to write "CSC 456" or "656" in the subject heading. Our Systems administrators are working on ways to filter out the every-increasing flow of spam to our accounts, but they haven't solved the problem yet.

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

Today we will continue our discussion of polynomial time complexity and NP-completeness.

L_3-cnf-sat is NP-complete.

Certificates.

Thursday, April 29, 2004

Tuesday, May 4, 2004

Today I will attempt to prove that boolean satisfiability is NP-complete.

Thursday, May 6, 2004

Work Assignment 5 by the beginning of class today.

If time permits, I will do the following today:

1. Let [G] be the encoding of a grammar. The language of all strings of the form [G]w such that G is a context free grammar and w is a string generated by G is decidable. (In fact, it is in the class P.)
2. The language of all strings of the form [G₁][G₂] such that G₁ and G₂ are context-free grammars and G₁ is not equivalent to G₂ is recursively enumerable. (But it is undecidable, because on the result below.)
3. The language of all strings of the form [G₁][G₂] such that G₁ and G₂ are context-free grammars and G₁ is equivalent to G₂ is not recursively enumerable, and hence undecidable. (This proof is very long, so I will only briefly sketch it.)

Tuesday, May 11, 2004

Final Examination: 10:10-12:10

Read the study guide.

challenge problems are absolutely due today.

Monday, May 17, 2004

The final grades are now finished.