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