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:
  1. Boolean satisfiability is in the class NP, since a satisfying assignment can be verified in polynomial time.
  2. 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.
  3. 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.