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 2013
Assignments and Lecture Topics

Revised May 14, 2013

Tuesday, January 22, 2013
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 24, 2013
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 29, 2013
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 31, 2013
Turn in Assignment 1 at the beginning of class today.
Tuesday, February 5, 2013
Today, I will go through the algorithm for minimizing a DFA.
We will begin the discussion of context-free grammars and languages.
Thursday, February 7, 2013
We will continue our discussion of context-free grammars and languages.
Tuesday, February 12, 2013
Turn in Assignment 2 at the beginning of class today.
Thursday, February 14, 2013
handout in pdf form
handout in postscript form
Tuesday, February 19, 2013
Thursday, February 21, 2013
Turn in Assignment 3 at the beginning of class today.
Examination today. Postponed.
I found a website that explains a lot of stuff in detail, using the exact same grammar and parse table I gave you for one of the examples.
The example given on that page, the sequence of configurations of the parser for the input string a*(b+c), has a few errors. The corrected computation.
Today we will go over the pumping lemma. We can use the pumping lemma to prove that certain languages, such as the language of all strings of the form anbn, are not regular.
If time permits, we will also go over the pumping lemma for context-free languages. We can use the pumping lemma for context-free languages to prove that certain languages, such as the language of all strings of the form anbncn, are not context-free.
If there is still more time, we will start on the CYK Algorithm.
Tuesday, February 26, 2013
We will probably spend the time reviewing material and filling details that were missed.
Wednesday, February 27, 2013
I will be in and out (mostly in) my office today between now (11:08) and 6:45 this evening. Feel free to come by. You can phone me at 895-1096 if you want to make sure I'm there.
Thursday, February 28, 2013
Examination today.
practice examination in pdf form
practice examination in postscript form
Highest score: 240
75 percentile score: 200
Median score: 174
25 percentile score: 155
Mean score: 177
Tuesday, March 5, 2013
Today we will begin the discussion of undecidability.
We will begin by introducing Turing machines and the Church-Turing thesis.
Thursday, March 7, 2013
Tuesday, March 12, 2013
Turn in Assignment 4 at the beginning of class today.
I will give the complete proof that the halting problem is undecidable. This is by far the most important single thing you need to learn in the course, so I will repeat this proof at least two more times before the end of the semester.
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.)
A nice slide show
Thursday, March 14, 2013
Today, we will get into the "nitty-gritty" of Turing machines. We will show various Turing machines that compute simple functions, such as reversing a string or incementing a binary numeral.
If time permits, I will introduce the concept of an enumerator.
When I was young, I learned that "enumerable" means "countable," and that every subset of an enumerable set is enumerable.
That's true. But can you actually find the enumeration?
Suppose I ask you to list all the positive integers in order. Can you do it? Well, you might complain that it would take forever, but you could certainly design a machine that would do it. The machine would run forever, of course, but it would correctly print all the positive integers, and in canonical order. (Well, really, it would print the numerals for the positive integers.)
But what if you wanted to enumerate some subset of the positive integers? For example, the odd numbers? No problem. The prime numbers? Of course, you could do it, but your machine would be a bit more complex. Some other set of positive integers? Why not?
Tuesday, March 19, 2013
Thursday, March 21, 2013
Tuesday, April 2, 2013
Thursday, April 4, 2013
Tuesday, April 9, 2013
Thursday, April 11, 2013
Examination today.
practice examination in pdf form
practice examination in postscript form
Highest score: 255
75 percentile score: 212
Median score: 175
25 percentile score: 150
Mean score: 183
Tuesday, April 16, 2013
Thursday, April 18, 2013
Tuesday, April 23, 2013
Thursday, April 25, 2013
Tuesday, April 30, 2013
Thursday, May 2, 2013
Tuesday, May 7, 2013
Turn in Assignment 5 at the beginning of class today.
Thursday, May 9, 2013
Tuesday, May 14, 2013
Final Examination, 6:00 to 8:00.
Practice final in pdf form
Practice final in postscript form
Oops -- I just now (Tuesday) discovered that the TM in Probem 41 does not do what I wanted it to do. It is too late to fix it. However, the TM on the actual final exam (that is, if there is one) does do what I wanted it to do -- I checked it yesterday.

Back to
Course Page