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

Computer Science 456/656
Automata and Formal Languages
Fall 2010
Assignments and Lecture Topics

Revised December 15, 2010

Tuesday, August 24, 2010
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.
Thursday, August 26, 2010
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 and non-deterministic finite automata (NFAs).
We state the Equivalence Theorem of Kleene, Rabin, and Scott.
Tuesday, August 31, 2010
We will give formal definitions of DFA and NFA today.
Today, we will go over the closure properties of the class of regular languages.
We will then continue this discussion, introducing regular expressions.
Thursday, September 2, 2010
Turn in Assignment 1 at the beginning of class today.
Today we will get started in proving the Equivalence Theorem. We will show how to construct a DFA equivalent to a given NFA. An NFA with n states is equivalent to a DFA with 2n states, although that number can usually be reduced by minimization.
Tuesday, September 14, 2010
Turn in Assignment 2 at the beginning of class today.
Thursday, September 16, 2010
Today we will continue our discussion of context-free languages and push-down automata.
Tuesday, September 21, 2010
Thursday, September 23, 2010
Examination today.
First exam, Fall 2007: in postscript form pdf form
First exam, Fall 2008: in postscript form pdf form
First exam, Spring 2009: in postscript form pdf form
I may ask a question about the CYK algorithm.
Please do not hesitate to send me email if you have a question about the material on the exam.
Tuesday, October 5, 2010
Today's handout in
postscript form
pdf form
Tuesday, October 12, 2010
Turn in Assignment 3 at the beginning of class today.
Tuesday, October 26, 2010
Turn in Assignment 4 at the beginning of class today.
Thursday, October 28, 2010
Examination today.
Practice exam in postscript form pdf form .
Please do not hesitate to send me email if you have a question about the material on the exam.
Thursday, November 18, 2010
The block sorting problem.
The Boolean circuit problem.
Tuesday, November 23, 2010
Turn in Assignment 5 at the beginning of class today.
Tuesday, December 7, 2010
Final Examination, 6:00 to 8:00.
Practice final in postscript form.
Practice final in pdf form.
Wednesday, December 15, 2010
I have computed the semester grades and entered them into the MyUNLV system. If anyone cannot access that system and still wants his or her grade, please send me email.

Back to Course Page