University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

Computer Science 456/656
Automata and Formal Languages
Spring 2018
Assignments and Lecture Topics

Revised May 15, 2018

Wednesday, January 17, 2018
Today we will overview the course. The two most important key words of the course are language and computable. We will start by discussing languages.
English, Spanish, Chinese, and other natural languages, are not part of this course. Programming languages are, however.
We will introduce deterministic finite automata (DFAs) and regular languages.
Monday, January 22, 2018
Assignment 1 is postponed because textbooks were not available in the bookstore.
Today, I will go through the algorithm for minimizing a DFA.
We will instruduce non-deterministic finite automata (NFAs).
Today, I will go through the algorithm for transforming an NFA to an equivalent DFA.
Wednesday, January 24, 2018
Turn in Assignment 1 at the beginning of class today.
Today we will discuss the operations of union, concatenation, and Kleene closure on languages. The class of regular languages is closed under those three operations.
We will introduce regular expressions.
We state the Equivalence Theorem of Kleene, Rabin, and Scott.
We give the algorithm for minimizing a DFA.
We give the algorithm for finding a DFA equivalent to a given NFA. Today we will discuss the operations of union, concatenation, and Kleene closure on languages. The class of regular languages is closed under those three operations.
We will introduce regular expressions.
We state the Equivalence Theorem of Kleene, Rabin, and Scott.
We give the algorithm for minimizing a DFA.
We give the algorithm for finding a DFA equivalent to a given NFA.
Monday, January 29, 2018
Today I will introduce regular expressions.
We will discuss the pumping lemma and use that lemma to prove that there are non-regular languages.
Note: there are two pumping lemmas: one for regular languages and one for context-free languages. This one is for regular languages.
We will instruduce context-free languages (NFAs).
Question for you to ponder. Modern programming languages are not context-free. However, in the back of your programming textbook, you might find a context-free grammar for the programming language, sometimes given in the form of "railroad" diagrams. Isn't that a Contradiction?
Wednesday, January 31, 2018
Turn in Assignment 2 at the beginning of class today.
Monday, February 5, 2018
Wednesday, February 7, 2018
Turn in Assignment 3 at the beginning of class today.
Monday, February 12, 2018
Wednesday, February 14, 2018
Turn in Assignment 4 at the beginning of class today.
Wednesday, February 21, 2018
Today we will talk about NP-completeness. I will start by introducing the concept of reduction. (If you reduce Problem X to Problem Y, then you can solve Problem X by finding a solution to Problem Y.) We are only interested in polynomial time reductions. That is, if it takes too much time to reduce an instance of Problem X to an instance of Problem Y, then that reduction might be useless.
Monday, February 26, 2018
Today we will continue talk about NP-completeness.
Richard Karp proved that SAT is NP-complete. Just know it's true.
You can prove that 3-SAT is NP-complete, by reducing SAT to 3-SAT in polynomial time. I order to do that, you need a context-free grammar for the language of all Boolean expressions, which respects the semantics of those expressions.
I will give a polynomial time reduction of 3-SAT to the independent set problem. This will prove that the independent set problem is NP-complete.
Wednesday, February 28, 2018
Turn in Assignment 5 at the beginning of class today.
Not all the answers have been given in class. You will need to do some research.
Monday, March 5, 2018
Turn in The rest of the true false problems at the beginning of class today.
Again, you might still need to do some research.
Polynomial time reduction of SAT to 3-SAT.
I will finish up the proof that the halting problem is undecidable. Using that fact, I will prove that there exists a mathematical statement which is true but has no proof. I will also prove that there is no limit to how long the shortest proof of a provable mathematical statement could be.
If time permits, I will introduce Turing machines. and the Church-Turing thesis. which states that anything that can be computed can be computed using a Turing machine.
No one would ever use Turing machines to do any computation in practice. So why do we study them?
Monday, March 12, 2018
iTurn in Assignment 7 at the beginning of class today.
I should be able o convince you that the Church-Turing thesis is true, but I cannot give a formal proof. I'll spend some time trying to convince you.
The proof of the Cook-Levin theorem, namely that SAT is NP-complete, can be found here. I will not present it in class, because it is quite lengthy, although very straightforward. Nevertheless, you should know (basically) how it works.
Wednesday, March 14, 2018
If you didn't turn it in on Monday, turn in Assignment 7 at the beginning of class today.
We can prove that the knapsack problem (KP) is NP-complete by reduction of the independent set problem to KP.
  1. What does each of these Turing machines do?
    1. Example 1 pdf format
    2. Example 2 pdf format
    3. Example 3 pdf format
    4. Example 4 pdf format
    5. Example 5 pdf format
    6. Example 6 pdf format
  2. Give a polynomial time reduction of the knapsack problem to the partition problem.
  3. Give a polynomial time reduction of the independent set problem to the knapsack problem.
  4. Give a polynomial time reduction of 4-CNF-SAT to 3-CNF-SAT.
  5. Give a polynomial time algorithm for 2-CNF-SAT.
  6. The updated parsing handout in postscript format
    The updated parsing handout in pdf format
Wednesday, March 21, 2018
Midterm examination today.
Practice Midterm
Monday, March 26, 2018
The midterm examination is now graded.
55 students took the examination. Scores are as follows:
365 possible
095 lowest
175 25 percentile
225 50 percentile (median)
280 75 percentile
315 highest
212 average
I was appalled by the number of students who missed problem 10. I am quite discouraged about this. This problem goes to the heart of the course. You must learn how to construct a context free grammar. The example I gave was so simple that there is no excuse!
Wednesday, April 11, 2018
Surprise quiz today.
Of those who took the examination:
77: Average
45: 25 percentile
75: 50 percentile
110: 75 percentile
150: Highest
160: Possible
Hand in Homework 8 in class today. Print the file, fill in the answers, and hand it in. (You can staple extra sheets to it if necessary, but it shouldn't be necessary.)
Nobody has sent me email asking questions. I guess you already know everything!
Answers to the suprise quiz in postscript format. Answers to the suprise quiz in pdf format.
Wednesday, April 18, 2018
Read discussion of the P=NP problem.
postscript format.
Read this discussion of NP-completenes. .
Monday, April 23, 2018
Turn in Assignment 9 at the beginning of class today.
Wednesday, April 25, 2018
Turn in answers to these questions in class today.
postscript format,
Answers.
Answers in postscript format.
Monday, April 30, 2018
There will be an ABET assessment test today. It is only 15 minutes, and does not count for your grade. I will lecture both before and after the test.
Thursday, May 3, 2018
There is a faculty candidate speaking at 11:00. I will be in my office before 11, and from 12:30 to 2:00.
Wednesday, May 2, 2018
Last day of class.
Monday, May 7, 2018
I plan to hold office hours today, starting in the morning and ending in the afternoon, perhaps from 10:00, or earlier, to 2:00, or even later, if there is a need. Send email if you want to see me and those hours are not convenient for you.
Oops, I forgot, there is a talk by a visiting faculty candidate at 1:00. I will be in my office up until about 12:45, and back in my office after the talk.
Wednesday, May 9, 2018
Final exam today. 10:10 to 12:10.
Practice Final in pdf format
Practice Final in postscript format
Tuesday, May 15, 17:37:28 PDT 2018
I just now submitted the grades. You should be able to obtain your grade through myunlv.

Back to Course Page