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
Spring 2010
Assignments and Lecture Topics
Revised March 27, 2010

-
Tuesday, January 12, 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, January 14, 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, January 19, 2010
-
We will give formal definitions of DFA and NFA 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.
-
Thursday, January 21, 2010
-
Turn in Assignment 1 at the beginning of class today.
-
Tuesday, February 2, 2010
-
Turn in Assignment 2 at the beginning of class today.
-
Tuesday, February 9, 2010
-
Turn in Assignment 3 at the beginning of class today.
-
Thursday, February 11, 2010
-
Examination today.
- First exam, Fall 2007:
in postscript form pdf form
-
First exam, Fall 2010:
in
postscript form
pdf form
-
First exam, Spring 2009:
in
postscript form
pdf form
-
Please do not
hesitate to send me email if you have a question about the material on the exam.
-
Tuesday, March 2, 2010
-
Turn in Assignment 4 at the beginning of class today.
-
Thursday, March 4, 2010
-
Today's handout in
postscript form
pdf form
-
Tuesday, March 9, 2010
-
Turn in Assignment 5 at the beginning of class today.
-
Tuesday March 16, 2010.
-
We will discuss the
Church-Turing thesis.
-
Thursday March 18, 2010.
-
Turn in Assignment 6 at the beginning of class today.
-
Today we will prove the main theorem of the course, namely that
the halting problem is undecidable.
In preparation for this lecture, it would be helpful to read about
binary encoding of Turing machines.
Also, to get into the right mood for the
diagonization
proof of the undecidability of the halting problem, read about the
Guardian of the Bridge who was
"
doomed to guard this bridge until truth and lies are one."
(Thanks to Emily Rodda.)
-
Tuesday March 23, 2010.
-
We prove that a language is recursively enumerable if and only if
it is accepted by some Turing machine.
-
Thursday, March 25, 2010
-
Examination today.
Practice exam
in
postscript form
pdf form .
-
This practice exam was designed for my class during the Spring Semester of
2009. Unfortunately, we have not gotten as far in the course this Semester.
Thus, there are several topics that are on the practice exam that we have
not covered.
-
I will cover some of those missing topics on Tuesday, March 23.
If there is any topic that I don't cover by that time, there will be no
question about that topic on the exam.
-
Tuesday, May 4, 2010
- Final Examination, 3:10 to 5:10.
-
Practice final in postscript form.
-
Practice final in pdf form.

Back to
Course Page