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