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
