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 2005
Assignments

Revised December 8, 2005

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 30, 2005.
Today we will broadly discuss the course as a whole.
We will then introduce the basic concepts of symbol, alphabet, and language, followed if time permits, by the concepts of finite state machine and regular language.
Discussion question of the day: What is the most important thing you will learn in this course?
Goals: Regular Languages.
Thursday September 1, 2005.
Today we will discuss acceptance of a language by a machine, and emphasize the difference between a DFA and an NFA.
Tuesday September 6, 2005.
Today we will discuss regular expressions. Goals: Regular Languages is now updated.
Thursday September 8, 2005.
Turn in Assignment 1 at the beginning of class today.
Today I will give two algorithms I promised you: It is important to note that every DFA is an NFA, but not vice-versa.
Tuesday September 13, 2005.
Today, we give two techniques for analyzing the regularity of languages.
Suppose L is a language over an alphabet Sigma. If u and v are strings, we say that u and v are L-equivalent if, for any string w over Sigma, uw is in L if and only if vw is in L. Theorem: If L is regular, there are finitely many L-equivalence classes, and the number is equal to the number of states of the minimal DFA that accepts L. Furthermore, if L is not regular, there are infinitely many L-equivalence classes. Thus, it is possible to prove that a language L is not regular by proving that there are infinitely many L-equivalence classes.
Another method of proving that a language is not regular is by use of the pumping lemma for regular languages. I will state and prove the pumping lemma today.
Thursday September 15, 2005.
Tuesday September 20, 2005.
You should work Study Problems 1 by the beginning of class today. Do not turn them in, since we have an examination today.
Here are additional study problems in regular languages.
Examination today. The exam will cover all material up until this point in the course.
Thursday September 22, 2005.
I hand back the graded exam.
Today we will give an introduction to context-free grammars.
Context-free grammars were originally developed in an attempt to analyze natural languages. Although that problem has never been solved, context-free grammars are quite useful for describing a number of useful artificial languages, such as various languages of algebraic expressions.
Tuesday September 27, 2005.
Today we will continue our discussion of context-free languages and context-free grammars.
Thursday September 29, 2005.
Today we will discuss the relation between syntax and semantics in context-free languages.
If time permits, I will dicuss PDAs and parsers.
Tuesday October 4, 2005.
Turn in Assignment 2 at the beginning of class today.
Here are additional study problems in context-free grammars.
Today we will make up material we missed last Thursday.
Thursday October 6, 2005.
Today we will discuss non-deterministic top-down and bottom-up parsers. Obviously, no one can implement a non-deterministic parser in a compiler, so this dicussion seems to be of no practical importance. But it does.
Tuesday October 11, 2005.
For those complaining about lack of partial credit, here is a quote from a famous mathematician:
"Words differently arranged have a different meaning and meanings differently arranged have a different effect."
Pascal, Blaise (1623-1662)
W. H. Auden and L. Kronenberger (eds.) The Viking Book of Aphorisms, New York: Viking Press, 1966.
Thanks to my former student Dean Bartkiw, who pointed me to a page of quotations from famous mathematicians on the web.
Today, I will introduce the Cocke-Younger-Kasami (CYK) algorithm. Given a context-free grammar G and a string w, the CYK algorithm determines whether w is generated by G. It also produces a parse tree for w; in fact, if G is ambiguous, it produces all possible parse trees.
The CYK algorithm is explained here and also here.
If time permits, I will state and prove the pumping lemma for context free languages.
William Shakespeare, you have met your match!
Thursday October 13, 2005.
Today we will continue our discussion of context-free languages.
We will also do the pumping lemma for context free languages.
Tuesday October 18, 2005.
Turn in Assignment 3 at the beginning of class today.
We will discuss parsers in depth. Although that subject naturally fits into the course at the point, I will postpone it for the following reasons:
With the above in mind, today I will introduce a new class of machines, namely Turing machines. Informally, a Turing machine (abbreviated TM) is a machine with finitely many memory states in its control, with a read-write head that can move in both directions along a tape of unlimited size, with the restriction that the tape contains only a finite amount of information. Any machine of any type, regardless of its complexity, can be emulated by some Turing machine.
Clasically, the tape of a Turing machine is "semi-infinite," meaning that it has a left-most cell, but extends infinitely to the right. But the Wikipedia definition allows the tape to extend infinitely to the left, also.
Please do not become confused by this difference. There are several definitions of Turing machine out there, but they are all equivalent. I mean that if M1 is a machine that is a Turing machine as defined by Wikipedia (or whatever), then M1 can be emulated by a machine M2 which is a Turing machine as defined by the Stanford Encyclopedia (or whatever), and the emulation requires at most a constant slowdown.
Thursday October 20, 2005.
Today we will continue the discussion of Turing machines and computability.
Tuesday October 25, 2005.
Today we will continue the discussion of Turing machines and computability.
Thursday October 27, 2005.
We will continue our discussion of Turing machines and computability.
We will discuss enumerators and enumeration.
Tuesday November 1, 2005.
Today we will prove 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.)
Does infinity exist?
Thursday November 3, 2005.
You should work Study Problems 2 by the beginning of class today. Do not turn them in, since we have an examination today.
Examination today.
Study guide for this exam.
Study guides for past semesters.
Tuesday November 8, 2005.
We will review the relation between enumerators and decidability.
We will define reduction, and mention some its uses. Reduction is important, and will be used frequently during the remainder of the semester.
Thursday November 10, 2005.
Today, I will continue to talk about reduction and "hardness."
I will give a precise definition of the well-known term, "NP-complete."
I will introduce the "root" NP-complete problem, Boolean Satisfiability.
Tuesday November 15, 2005.
Today, we will introduce Lsat, the subset of Lbool consisting of all satisfiable Boolean expressions.
We will first give a rigorous and precise definition of NP-completeness, and then we will state that Lsat is NP-complete. After that, we will prove, by reduction, using the hypothesis that Lsat is NP-complete, that certain other problems are also NP-complete.
Thursday November 17, 2005.
Turn in Assignment 4 at the beginning of class today.
Today, we will prove that Lsat is NP-complete. The proof will depend on the grammar you worked out for Assignment 4.
Take a look at:
Tuesday November 22, 2005.
Today we will complete the proof that 3-cnf-sat is NP-complete, by reducing Boolean satisfiability to it.
Some examples of 3-cnf equivalents of simple Boolean expression.
An outline of the reduction proof that we will give in class.
Thursday November 24, 2005.
Thanksgiving Day holiday.
Tuesday November 29, 2005.
Today I will introduce general grammars.
If time permits, I will begin the detailed discussion on parsing. A parser is a machine which reads in a string and constructs a derivation of that string using a given grammar. We will discuss deterministic parsers that are used in practice. I will concentrate on a standard kind of parser called an LALR parser.
In order for a parser to be of practical use, it must
  1. be deterministic,
  2. be fast,
  3. have finite lookahead,
  4. be able to parse the underlying context-free grammar of a modern programming language.
Here is an LALR parser. The third page contains a table without entries for an LALR parser for a different grammar. This other grammar is ambiguous, containing the "dangling else" problem, but the LALR parser, if properly designed, will unambiguously parse any string by resolving the "else" problem in the proper way.
Here is the PDF version.
Thursday December 1, 2005.
Turn in Assignment 5 at the beginning of class today.
Tuesday December 6, 2005.
Today we will try to finish any unfinished material, and begin to summarize the course.
Thursday December 8, 2005.
Work Assignment 6 by today, but do not turn it in.
Due to ISPAN 2005, which is held in Las Vegas this week, I will have truncated office hours today.
We will finish the summary of the course.
Tuesday, December 13.
Final Examination.
Practice final in postscript form.
Practice final in pdf form.
Our final examination is scheduled for 6:00 PM. The examination will be comprehensive.

Back to Course Page