University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 456/656
Automata and Formal Languages
Fall 2008
Assignments
Revised December 15, 2008

-
Background.
It is important to have a fundamental understanding of logic
and the language of proofs, as well as basic (grade school)
understanding of set theory.
There is substantial amount of background material in Chapter 0 of your
textbook, although that chapter also contains material that I do not
expect you to know already, such as the definition of an automaton.
Tuesday August 26, 2008.
Alphabets, strings, and languages.
Regular languages, DFAs, and regular expressions.
Thursday August 28, 2008.
Due to an unusual situation, no office hours today.
Today, we will continue our discussion of regular languages,
regular expressions, and DFAs. We will also introduce NFAs.
Tuesday September 2, 2008.
Chitwan Gupta will be out of town this week.
Today we will go over the algorithm that finds a minimal DFA.
Today we will go over the contruction of a DFA equivalent to a given NFA.
Thursday September 4, 2008.
Chitwan Gupta will be out of town this week.
Turn in Assignment 1 at the beginning of class today.
Tuesday September 9, 2008.
figure from class in postscript form
figure from class in pdf form
Thursday September 11, 2008.
Turn in Assignment 2 at the beginning of class today.
Thursday September 18, 2008.
Turn in Assignment 3 at the beginning of class today.
Tuesday September 23, 2008.
Turn in Assignment 4 at the beginning of class today.
Thursday September 25, 2008.
Examination.
Tuesday October 7, 2008.
Parsing handout in postscript form.
Parsing handout in pdf form.
Thursday October 9, 2008.
Turn in the completed LALR parser from the third page of the parsing handout.
Tuesday October 14, 2008.
We will discuss the
Church-Turing thesis.
Thursday October 16, 2008.
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 October 21, 2008.
We prove that a language is recursively enumerable if and only if
it is accepted by some Turing machine.
Thursday October 23, 2008.
We will start talking about the polynomial time class.
Tuesday October 28, 2008.
Before we get back to the polynomial time class, we will deal with
some more computability questions.
-
What does it mean to say that a real number is computable?
-
Most people would agree that every rational number should be called
"computable," despite the fact that the decimal expansion of a rational
number might not terminate. But what about pi?
-
Yes, it is certainly true that we cannot write down all the decimal
digits of pi. But the same thing is true for all the integers.
We cannot write down all the integers, but we can write down
the next integer.
-
Maybe the question should be phrased in terms of computability of comparisons.
Suppose x is a real number. Is it possible to figure
out whether any given rational number is less than x?
More precisely, is the set of all encodings of fractions whose values
are less than x a decidable language?
That is certainly true if x = pi.
For example, it can be easily seen that the string "25/8"
is in the language, while "22/7" is not.
-
Is computability of comparisons the same as ability to enumerate the
decimal digits?
Thursday October 30, 2008.
Boolean Satisfiability will be today's subject.
I want to remind everyone to think about turning in a
challenge problem.
I will probably update that list before the end of the semester.
Tuesday November 4, 2008.
You do not want to miss the lecture today.
We will cover both pumping lemmas, showing their similarities and differences.
Using the pumping lemma for context free languagues, we will prove
that {anbncn} is not context free.
Thursday November 6, 2008.
Examination.
Tuesday November 25, 2008.
Turn in Assignment 5 at the beginning of class today.
Tuesday, December 9, 2008.
Final Examination.
The final examination is scheduled for 3:10 PM.
The examination will be comprehensive.
Study Guide for the Final
Monday, December 15, 2008.
True or False: Every subset of a regular language is regular.
Someone missed this one!
True or False: The complement of every P language is P.
That's true.
True or False: The complement of every NP language is NP.
Well, if P = NP, that's the same question, so it's true.
So you know that the answer for the test cannot be F.
As it turns out,
the question of whether P = co-NP is open.
So the correct answer for the test is O
No one got it right.
True or False: There is a mathematical theorem which has a proof,
but where the shortest proof has langth at least A(n), where n is
the length of the theorem and A is the Ackermann function.
True. Suppose not. Let L_halt be the halting problem.
Suppose M is a TM and w an input string for M. Then w is in L_halt
if and only if M halts with input w. Thus, if w is in L_halt,
there is a proof of that fact: namely, emulate M on w until it halts.
Let n be the length of the string w. Try all possible proofs of lengths
at most A(n). (The amount of time required for this is "beyond boggle,"
but still finite.) Then w is in L_halt if and only if you find a proof
in one of those finitely many attempts.
Thus, L_halt is decidable. Contradiction.
Yes, the final exams are graded.
No, I won't have your grades until tomorrow afternoon.

Back to
Course Page