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.
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