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
Fall 2016
Assignments and Lecture Topics
Revised December 12, 2016

-
Monday, August 28, 2016
-
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.
-
-
Wednesday, August 31, 2016
-
We will introduce
non-deterministic finite automata (NFAs).
-
Today, I will go through the algorithm for minimizing a DFA.
-
Today, I will go through the algorithm for transforming an NFA to an
equivalent DFA.
-
Monday, September 5, 2016
- Labor Day Recess
-
Monday, September 19, 2016
-
Turn in Assignment 1 at the beginning of class today.
-
Wednesday, September 21, 2016
-
Turn in Assignment 2 at the beginning of class today.
-
Wednesday, September 28, 2016
-
Turn in Assignment 3 at the beginning of class today.
-
Wednesday, October 5, 2016
-
Examination today.
-
Wednesday, October 12, 2016
-
Turn in Assignment 4 at the beginning of class today.
There is one problem that deals with the CYK algorithm, which we have not
gone over. So, you don't have to do that one.
-
Monday, October 17, 2016
-
Some parking lots will be closed today, and the overflow might choke the parking lots near TBE.
I will be in class if I can find a parking space.
-
I am here, so there will be class.
-
Wednesday, October 19, 2016
-
Class is canceled today because of the presidential debate on campus.
-
Wednesday, October 26, 2016
-
Turn in Assignment 5 at the beginning of class today.
-
Turn in Assignment 6 at the beginning of class today.
-
My afternoon office hour is canceled today.
-
Monday, November 7, 2016
-
Turn in Assignment 7 at the beginning of class today.
No excuses! It's all on Wikipedia!
-
Wednesday, November 9, 2016
-
Examination postponed.
-
Monday, November 14, 2016
-
Examination today.
-
I gave three exams during the Fall semester of 2013.
Our exam on Monday will somewhat overlap both the second and the third
exams of Fall 2013.
-
Fall 2013 practice second examination in postscript form.
-
Fall 2013 practice second examination in pdf form.
-
This is the third practice examination of Fall 2013. On Monday's test,
I will not ask any question that deals with material we have not covered.
-
Fall 2013 practice third examination in postscript form.
-
Fall 2013 practice third examination in pdf form.
-
I gave only two exams during the Spring semester of 2013.
The following is much closer to what the exam on Monday will be like.
However, I won't give any question on the test that refers to material
we haven't covered.
-
Spring 2013 practice examination in pdf form
-
Wednesday, November 30, 2016
This NP handout contains most of what I have
given in class about the class NP. But it does contain a few things that I
would like to update, by changing notation slightly. I'll let you know.
Theorem 7, starting on page 8 of that handout, is what I was trying to prove
in class today. The equivalences I was trying to remember
start at the bottom of page 9.
I will add more here before Monday.
Finishing up the lecture on reduction of
SAT to 3SAT.
-
Monday, December 5, 2016
-
Turn in Assignment 10 at the beginning of class today.
No excuses! It's all on Wikipedia!
-
Thursday, December 8, 2016
-
I tossed and turned last night, until I found the reduction of
the knapsack problem to the partition problem. (It's easy, of course.)
-
Here it is, on page 15:
-
Wednesday, December 14, 2016, 8:00 AM
-
Final Examination today.
-
Practice Final
-
The practice final is much longer and harder than the real final.

Back to
Course Page