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.
-
-
What does each of these Turing machines do?
-
Example 1
pdf format
-
Example 2
pdf format
-
Example 3
pdf format
-
Example 4
pdf format
-
Example 5
pdf format
-
Example 6
pdf format
-
Give a polynomial time reduction of
the knapsack problem to the partition problem.
-
Give a polynomial time reduction of
the independent set problem to the knapsack problem.
-
Give a polynomial time reduction of 4-CNF-SAT to 3-CNF-SAT.
-
Give a polynomial time algorithm for 2-CNF-SAT.
-
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