University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 456/656
Automata and Formal Languages
Spring 2003
Assignments
Revised May 8, 2003

-
Tuesday, January 21, 2003
-
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 23, 2003
-
We will continue our discussion of
regular language, and introduce
regular expressions and
finite state machines.
-
Discussion question of the day:
Why do introduce the concept of
a "language"?
-
Tuesday, January 28, 2003
-
We will discuss regular expressions today.
finite automata today and for the next several
days.
We will cover the material of Part 2 of your textbook, pages 83-200.
-
Thursday, January 30, 2003
-
Turn in Assignment 1 at the beginning of class today.
-
We will discuss Kleene's Theorem today and Tuesday.
-
I will introduce the concept of proof by
structural induction.
-
Tuesday, February 4, 2003
-
We will continue our discussion of the equivalence of the three
characterizations of regular languages.
-
Turn in Assignment 2 at the beginning of class today.
-
Thursday, February 6, 2003
-
Today I will show how to minimize a finite automaton.
-
If time permits, I will begin discussing proofs of non-regularity.
-
Tuesday, February 11, 2003
-
Turn in Assignment 3 at the beginning of class today.
-
Thursday, February 13, 2003
-
We will continue discussing proofs of non-regularity.
-
We will spend some time reviewing past homework assignments.
-
Tuesday, February 18, 2003
-
-
We will spend some time today reviewing homework assignments.
-
Study guide for Thursday's examination.
-
Thursday, February 20, 2003
-
Work (but do not turn in)
Assignment 4 by the beginning of class today.
-
First Examination.
-
Tuesday, February 25, 2003
-
Today I will hand back the exams.
-
Today we will begin discussion of
context-free languages,
basically the material of Part 3 of your textbook, pages 201-315.
This subject will occupy most of our attention until the next examination.
-
Thursday, February 27, 2003
-
Today we will continue our discussion of context-free grammars and
context-free languages.
Be sure to read Sections 6.1, 6.2, 6.4, and 6.5.
-
Tuesday, March 4, 2003
-
Today we will continue our discussion of context-free grammars and
context-free languages.
Be sure to read Sections 6.3 and 6.6.
-
If time permits, we will begin discussion of push-down automata.
Be sure to read Sections 7.1 and 7.2.
-
Thursday, March 6, 2003
-
Turn in
Assignment 5 by the beginning of class today.
-
We will continue our discussion of push-down automata, including
deterministic push-down automata.
-
Tuesday, March 11, 2003
-
We will continue our discussion of push-down automata, including
recursive-descent parsers, such as
Example 7.5 on page 269 of your textbook, and
shift-reduce parsers, such as
Example 7.6 on page 271 of your textbook.
-
Thursday, March 13, 2003
-
If necessary, we will continue our discussion of push-down automata
and parsers, including the practical use of parsers.
LALR Parsers.
-
Tuesday, March 25, 2003
-
-
We will give an overview of computability.
-
Thursday, March 27, 2003
-
Turn in
Assignment 6
and Assignment 7
by the beginning of class today.
-
Today we will discuss Turing machines in detail. I will also try to convince
you of the Church-Turing thesis.
Read Chapter 9 of your textbook, pages 317 - 364.
We will continue our discussion of computability and Turing machines.
-
Tuesday, April 1, 2003
-
-
Today we will continue our discussing of Turing machines.
-
We will also discuss Thursday's exam.
-
Thursday, April 3, 2003
-
I will continue to introduce new material about computability and Turing
machines.
-
If time permits, I will spend some time discussing homework questions
on Turing machines.
-
Turn in
Assignment 8 by the beginning of class today.
- Doina will go over homework problems during the latter part of the class
period today.
-
Tuesday, April 8, 2003
- Second Examination.
- A solution to 9.15(c).
- Study guide for the examination.
-
A question that will be on the examination.
-
Thursday, April 10, 2003
- Today I will hand back the graded examination.
-
Tuesday, April 15, 2003
- Today we will discuss the concept of a
recursive real number.
-
Thursday, April 17, 2003
- What does it mean to say that a problem is
NP-complete?
Today we will begin discussion leading up to that very important concept.
-
Tuesday, April 22, 2003
- Today (backtracking to the subject of context-free languages),
I will introduce the pumping lemma
for context-free languages,
and use it to prove that certain languages are not context-free.
-
You will find context-free grammars for most programming languages
in various books. Yet, I have told you in class that modern programming
languages are never context-free.
What is going on?
-
Thursday, April 24, 2003
-
Today we will discuss the concept of NP-completeness in more detail.
-
Tuesday, April 29, 2003
-
Today we will prove that Boolean satisfiability is NP-complete, in the
following steps:
-
Boolean satisfiability is in the class NP, since a satisfying assignment
can be verified in polynomial time.
-
Fix M to be an NTM.
Consider the following question: can a given string w be accepted by
M in at most m steps?
We will show that, using M, w, and m as inputs, we can construct a Boolean
expression E, of complexity O(m2log(m)), which is satisfiable if and
only if w is accepted by M in at most m steps. Further, this construction
takes O(m2log(m)) time.
-
If L is a fixed NP-time language, then there is a fixed k and a fixed NTM M
such that, for any string w in L, M accepts w in at most nk steps,
where n is the length of w. It follows that, given any string w, there
is a Boolean expression E, of complexity O(n2klog(n)), where
n is the length of w, and where E is satisfiable if and only if w is in L.
Thus, by definition, Boolean satisfiability is NP-complete.
-
Thursday, May 1, 2003
-
Today, we will introduce the concept of a general grammar.
A language has a general grammar if and only if it is recursively
enumerable.
-
Today we will prove that 3-Sat is NP-complete, by given a polynomial
time reduction of Boolean satisfiability to 3-Sat. (It is trivial
that 3-Sat is NP.)
-
The Independent Set problem is trivially NP. We will show that
it is NP-complete, by constructing a polynomial time reduction of
the Independent Set problem to 3-Sat.
-
In
Richard Karp's original paper, he lists 21 NP-complete problems.
There are literally thousands of NP-complete problems known now.
-
Block sorting is NP-complete. A diagram, in red, blue and black,
illustrating the proof, is on Dr. Bein's office door, TBE B372 E.
-
Can you think of a recursive language which is not NP?
-
Tuesday, May 6, 2003
-
Turn in
Assignment 9 by the beginning of class today.
-
The formula in Exercise 14.7(b) on page 523 can be rewritten in
3-CNF form with only n clauses
-
what can be said about computability by parallel processors?
This problem could be of great practical importance in the future.
-
There is a
parallel processing analog of the "Is P = NP?" problem.
It is also open, and is also of immense importance.
We will discuss the Boolean circuit problem. This problem can be
decided in polynomial time, but parallel processors don't seem
to help. Yet, nobody has been able to prove that.
-
Thursday, May 8, 2003
- Students registered for CSC 656 are required to hand in their
graduate assignmenttoday.
-
Tuesday, May 13, 2003
- Final Examination, 10:10 to 12:10.
- Study guide for the examination.
