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

Revised December 20, 2006

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 29, 2006.
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?
Thursday August 31, 2006.
Today we will discuss acceptance of a language by a DFA, and introduce the concepts of regular expression and regular language.
Tuesday September 5, 2006.
Today we will learn how to minimize a DFA.
We will introduce the concept of a non-deterministic automaton (NFA).
We will learn how to construct a DFA equivalent to a given NFA.
We will discuss regular expressions in depth, and learn the equivalence of the three definitions of regular language.
Thursday September 7, 2006.
Even though we really tried, we didn't get through all the topics from last time, so we will finish them today.
Tuesday September 12, 2006.
Turn in Assignment 1 at the beginning of class today.
We will spend a few minutes discussing some of the problems in Assignment 1.
We will summarize the closure properties of the class of regular languages, including union, intersection, concatenation, Kleene closure, complementation, inversion, and homomorphism.
If time permits, we will then discuss the fact that many languages which are of practical importance are not regular, including most algebraic languages and programming languages. The pumping lemma, which you are expected to understand, can be used to prove that these languages are not regular.
Thursday September 14, 2006.
Today we will introduce the topic of context-free languages and context-free grammars.
Tuesday September 19, 2006.
Today we will continue our discussion of context-free languages and context-free grammars.
Thursday September 21, 2006.
Today we will continue our discussion of context-free languages and context-free grammars. In particular, we'll review the concept that a context-free grammar respects the semantics of a language.
This concept is limited to those languages which have semantics, of course.
Tuesday September 26, 2006.
Turn in Assignment 2 at the beginning of class today.
Thursday September 28, 2006.
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.
Here are additional study problems in context-free languages. Not all the material in that page has been covered in class. Material not mentioned in class will not be on the examination. For example, there will be no mention of the pumping lemma for context-free languages.
Examination today. The exam will cover all material up until this point in the course. This includes the pumping lemma for regular languages.
Tuesday October 3, 2006.
I will hand back the graded test today.
In whatever time remains, we will discuss the CYK algorithm for deciding a context-free language.
Thursday October 5, 2006.
Practice finding regular expressions for DFA's. (postscript) (pdf)
We will continue discussion of the CYK algorithm for deciding a context-free language.
We will introduce the concept of top-down and bottom-up parsing, using a stack machine.
Tuesday October 10, 2006.
We will postpone the topic of deterministic parsing of context-free languages, since it is very technical.
We will postpone the discussion context-sensitive languages until after we cover some basic topics in computability.
Today, we will discuss Turing machines and computability. I will start with an informal overview of the entire subject.
Thursday October 12, 2006.
As practice, work this CYK instance by Tuesday. (postscript) (pdf)
We will continue our discussion of Turing machines and computability. We will return to this topic after we finish with parsing.
Tuesday October 17, 2006.
Today, we will discuss deterministic LR (bottom-up) parsing. A Wikipedia site. Another Wikipedia site.
Thursday October 19, 2006.
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.
Tuesday October 24, 2006.
Today we will devote the lecture to an intensly detailed discussion of LALR parsers.
Thursday October 26, 2006.
Turn in Assignment 3 at the beginning of class today.
Today, we will introduce the pumping lemma for context-free languages.
The topic of context-sensitive grammars will be postponed until after the examination.
Study guide for the first examination of the Spring.
Study guide for the second examination of the Spring.
Tuesday October 31, 2006.
Examination today.
Study guide for this examination.
Thursday November 2, 2006.
Today, we will return to the question of computability.
We will go over enumerability, and relate enumerability and Turing machines.
Concepts we will discuss today include
  1. Recursive
  2. Recursively enumerable
  3. Undecidable
Tuesday November 7, 2006.
Today, we will continue our discussion of undecidability.
Thursday November 9, 2006.
I will hand back the exams today.
Tuesday November 14, 2006.
Today we will backtrack to regular languages. We will spend some time on a topic that was poorly understood on the last exam, namely the relation between finite automata and regular expressions.
This may be helpful while studying for the final examination:
Thursday November 16, 2006.
  • Today we will begin our discussion of complexity theory. We will define the complexity classes polynomial timeand non-deterministic polynomial time.
  • Tuesday November 21, 2006.
  • Today we will define reduction and NP-completeness.
  • Thursday November 23, 2006.
    Thanksgiving Day holiday.
    Tuesday November 28, 2006.
    Turn in Assignment 4 at the beginning of class today.
    Wikipedia study guide.
    Thursday November 30, 2006.
    Today we will give the definition of NP-complete. We will introduce the Boolean satisfiability problem, which will be our holotypical NP-complete problem.
    We will then introduce Boolean 3-CNF satisfiability, a somewhat simpler NP-complete problem that is easier to work with.
    Tuesday December 5, 2006.
    Turn in Assignment 5 at the beginning of class today.
    Today we will continue our discussion of NP-complete problems. We will show that the independent set problem is NP-complete, by reducing Boolean 3-SAT to it.
    Thursday December 7, 2006.
    This is the day to finish remaining topics that were missed.
    Tuesday, December 12.
    Final Examination. The final examination is scheduled for 6:00 PM. The examination will be comprehensive.
    Practice final in postscript form.
    Practice final in pdf form.
    Basic automata review.
    List of automata articles on Wikipedia.
    I plan to be in my office this afternoon.
    I am in my office now ( Tue Dec 12 14:13:27 PST 2006 ) and will be here most of the time until the exam starts.
    Wednesday, December 20.
    I have submitted the grades to the registrar. You can access them online.
    Have a Merry Christmas and a Happy New Year.

    Back to Course Page