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