Computer Science 456/656: Automata and Formal Languages
Spring 2002
Assignments
This page will be updated frequently.
Most recent update: May 1, 2002.
Turing Machine Emulation
-
Background.
You will be assumed to know the contents of sections 1.1 through 1.4,
pages 3-27 of your textbook.
-
Wednesday January 23, 2002.
-
Monday January 28, 2002.
-
Wednesday January 30, 2002.
Homework due.
Assignment 1 will be due in class today.
-
Monday February 4, 2002.
Homework due.
The first part of Assignment 2 is due in class today.
-
Wednesday February 6, 2002.
Homework due.
The second part of Assignment 2 is due in class today.
Today we will show how to minimize a DFA, and how to construct a DFA
equivalent to a given NFA.
-
Monday February 11, 2002.
Today we will review some of the material we introduced last week, and
work some more problems.
If time permits, we will discuss the construction of a regular expression
from a DFA.
-
Wednesday February 13, 2002.
Today I will explicitly list the portions of the textbook that will be
covered in the exam next week, and we will fill in some gaps in the
material in those chapters.
-
Wednesday February 20, 2002.
Work Assignment 3 by today, in preparation for the
exam, but do not turn it in.
I will be unable to be in my office during office hours this afternoon.
We will review various forms of the pumping lemma for regular languages,
as well as the other major themes of this portion of the course.
Some of those themes will be on the test. Very definitely, the pumping lemma
will be on the test.
-
Monday February 25, 2002.
I will be unable to be in my office during office hours this afternoon.
However, I plan to be available all morning in my office, starting
around 9:30.
There will be an examination today, covering regular languages, regular
expressions, automata, and a few other topics we discussed in class.
This material can be found in Chapters 1 through 5 of your textbook.
-
Wednesday February 27, 2002.
Today we will begin to discuss context-free languages, Chapter 6 in the
textbook.
After class today, one student asked me whether, given an ambiguous
context-free grammar, an equivalent unambaiguous context-free grammar can
always be found. This was an excellent question. The answer is no.
A context-free language that has no unambiguous context-free grammar is
called inherently ambiguous. A simple example of such
a language is the set of all strings of the form
aibjck
where i is not equal to j or j is not equal to k.
-
Monday March 4, 2002.
Assignment 4 is due in class today.
Today, we will continue our discussion of context-free languages.
-
Wednesday March 6, 2002.
Today we will introduce Push-Down Automata, and discuss their relationship
with context-free languages.
-
Monday March 11, 2002.
Assignment 5 is due in class today.
Today we will continue our discussion of Push-Down Automata. In particular,
we will prove Theorem 7.2 on page 212 of the textbook.
-
Wednesday March 13, 2002.
Anonymous email message are not acceptable. If you
send me an email message from an outside account, fine, but be sure
to include your real name.
Today we will begin the discussion of parsing. Read Section 7.6 of your
textbook, beginning on page 222.
-
Monday March 18, 2002.
We will continue our discussion of parsing.
We will also introduce the pumping lemma for context-free languages.
-
Wednesday March 20, 2002.
Assignment 6 is due in class today.
There will be an examination today, covering material in
Chapters 1 through 8 of your textbook, plus a small amount of additional
material introduced in the lectures.
-
Monday March 25, 2002.
Spring Break.
-
Thursday March 28, 2002.
I have finished grading the examination. The median score is 91 points,
out of 150 possible. A grade of 75 or higher indicates a performance
at the level of "C" or better.
-
Monday April 1, 2002.
We will begin Chapter 9 of your textbook.
-
Wednesday April 3, 2002.
We will continue discussion of Chapter 9 of your textbook.
-
Monday April 8, 2002.
Assignment 7 is due in class today.
Today we will continue our discussion of Turing machines.
We will show how Turing machines can emulate more complex machines.
-
Monday April 15, 2002.
Today we will continue our discussion of Turing machines.
-
Wednesday April 17, 2002.
Assignment 8 is due in class today.
We will continue our discussion of undecidability today, and also
introduce unrestricted grammars (also known as
general grammars or
phase-structure grammars).
-
Monday April 22, 2002.
-
Wednesday April 22, 2002.
Assignment 9 is due in class today.
-
Monday April 29, 2002.
We will discuss boolean satisfiability, which will be our "starting"
NP-complete problem.
-
Wednesday May 1, 2002.
Today we will prove that boolean satisfiability is NP-complete.
This is a very detailed proof from "first principles," not using
using reduction, since we have to start somewhere.
We will also prove that the clique problem is NP-complete, by reducing
boolean 3-satisfiability to the clique problem. This is a rather
simple proof, so we might do it first, even though it actually follows
the above. Many "reduction" proofs of NP-completeness are much harder,
but they tend to be in the same spirit as this one.

Back to
Course Page