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