University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

Computer Science 456
Formal Languages and Automata
Spring 2007
Assignments

Revised April 24, 2007

Overview
List of automata articles on Wikipedia.
Additional summary pages: (postscript) (pdf)
Tuesday, January 16, 2007
Today we will introduce the basic concepts of symbol, alphabet, and language, followed if time permits, by the concepts of finite state machine and regular language.
Thursday, January 18, 2007
Today we will discuss acceptance of a language by a DFA, and introduce the concept of regular expression.
Practice finding regular expressions for DFA's. (postscript) (pdf)
Tuesday, January 23, 2007
Today, we will talk about finite state machines, including deterministic finite automata and non-deterministic finite automata.
Every regular language is accepted by some DFA. Every regular language is accepted by some NFA. Every regular language has a regular expression.
If time permits, we will show how to minimize a DFA, and how to convert an NFA into an equivalent DFA.
Thursday, January 25, 2007
Turn in Assignment 1 at the beginning of class today.
We will discuss the closure properties of the class of regular languages, and their relation to regular expressions.
Tuesday, January 30, 2007
Today, we will discuss the pumping lemma, and use it to prove that a language is not regular.
Thursday, February 1, 2007
Today we will prove the pumping lemma, and use it to prove that some languages are not regular.
If time permits, we will begin the subject of context-free languages.
Tuesday, February 6, 2007
Today we will continue our discussion of context-free languages.
Thursday, February 8, 2007
Tuesday, February 13, 2007
Turn in Assignment 2 at the beginning of class today.
Thursday, February 15, 2007
Examination today. The exam will cover all material up until this point in the course. This includes the pumping lemma for regular languages.
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.
Tuesday, February 20, 2007
Today, we will learn the CYK algorithm.
I will start the discussion of parsers.
Thursday, February 22, 2007
Today, I will turn back the exams and discuss them.
We will continue the discussion of parsers.
Tuesday, February 27, 2007
We will continue the discussion of parsers, explaining the Action and Goto tables of an LALR parser, or shift-reduce parser, in detail.
Thursday, March 1, 2007
Today we will begin discussion of the main thrust of this course by discussing the concept of computability.
If time permits, I will introduce the pumping lemma for context-free languages.
Tuesday, March 6, 2007
Turn in Assignment 3 at the beginning of class today.
Today, we will discuss the emulations that justify the Church-Turing thesis.
Thursday, March 8, 2007
Tuesday, March 20, 2007
Today we will prove that the halting problem is undecidable.
Thursday, March 22, 2007
Turn in Assignment 4 at the beginning of class today.
Today we will talk about non-deterministic Turing machines. We will show the equivalence of deterministic and non-deterministic Turing Machines by using an Ariadne's string proof.
Tuesday, March 27, 2007
Today, we will discuss the pumping lemma for context-free languages and context-sensitive languages.
Thursday, March 29, 2007
Today we will be to discuss the computational complexity classes. A computational complexity class is a class of languages defined by its "hardness," i.e., how hard it is to determine that a string is in the language. We will only consider languages that are decidable, i. e., whether the computation can be done is not the issue, rather, how much of some resource (usually time or space) is needed to do the computation.
Computational Complexity of Games and Puzzles.
Tuesday, April 3, 2007
Today we will discuss the top of reduction in greater depth. I will carefully review two examples in detail, if time permits.
This leads directly into the definition of the class NP-TIME, known as simply "NP" for short, and of NP-completeness
Thursday, April 5, 2007
One of the most important facts for you to remember about this course is that some things are true but beyond reason. We can prove that fact by reduction.
Tuesday, April 10, 2007
Boolean satisfiability is NP-complete, and so is the restricted form of called 3-CNF-SAT, or just 3-SAT.
Today, I will prove that the independent set problem is NP-complete, by reducing 3-CNF-SAT to it.
Thursday, April 12, 2007
Examination today.
Study Guide for the Test
Tuesday, April 17, 2007
Today, I will hand back the examination.
Thursday, April 19, 2007
Here is a description of the complexity class NC. What is the meaning of "NC"?
Today, I will break with tradition and give a "slide lecture," that is, I will use a website on the screen to try to prove that Boolean satifiability is NP-complete.
If time permits, I will explain why Boolean 3-CNF-SAT is NP-complete, given that Boolean satisfiability is NP-complete.
Tuesday, April 24, 2007
Today I will introduce unrestricted grammars , also known as general grammars or phase structure grammars.
A language is accepted by some Turing machine if and only if it is generated by some unrestricted grammar.
Thursday, April 26, 2007
Time to start reviewing topics. We'll start from the beginning.
Tuesday, May 1, 2007
We will continue our review.
Thursday, May 3, 2007
You do not want to miss this class.
Tuesday, May 8, 2007
Final Examination: 3:10 -- 5:10
Study Guide for the Final