Computer Science 456/656: Automata and Formal Languages
Spring 2001
Assignments
This page will be updated frequently.
Most recent update: May 16, 2001.
Turing Machine Emulation
-
Background.
You will be assumed to know the contents of sections 1.1 through 1.4,
pages 3-27 of your textbook.
-
Wednesday January 17, 2001.
Today, we will give an overview of the course.
We will then introduce the concept of language.
Please read Section 1.5 of your textbook, pages 27-30.
If time permits, we will begin the topic of mathematical
induction.
-
Monday January 22, 2001.
Today we will introduce some elementary concepts involving languages,
including concatenation and Kleene closure.
We will also continue the discussion of mathematical induction.
Please read Chapter 2 of your textbook, pages 36-68.
-
Wednesday January 24, 2001.
Homework due.
Assignment 1
will be due on Wednesday, January 24, in class.
Today we will introduce regular expressions and
discuss the three definitions of regular language.
I have introduced the concept of finite automaton
(FA, or DFA) informally
in class, but you should try to understand the formal definition given
in the textbook.
-
Monday January 29, 2001.
Today we will introduce the concept of a non-deterministic
machine. A machine is deterministic if its action at each
step is determined by its state and its input at that step.
A non-deterministic machine may have any number of choices of action
for a given state and input.
We will conclude the discussion of the equivalence of the three definitions
regular language.
In particular, I will outline the proof that any language accepted by
an NFA with n states is also accepted by some DFA
which has at most 2n states.
Today is the day to ask any questions you might have about
Assignment 2.
-
Wednesday January 31, 2001.
Homework due.
Assignment 2
will be due on Wednesday, January 31, in class.
Today I will give the proof, using structural induction, that
every language generated by a regular expression is accepted by
some NFA.
I will introduce the concept of a minimal DFA and show
show to replace any DFA by an equivalent minimal DFA.
-
Monday February 5, 2001.
Assignment 3
will be due on Monday, February 5, in class.
Today we will give the proof that there exists a regular expression
for the language accepted by any FA.
Here is the proof.
We will also work through an example of minimizing an FA.
The textbook covers minimal finite automata in
Section 5.2, pages 140-144.
-
Wednesday February 7, 2001.
Today we will discuss ways to prove that a language is not regular.
Read Chapter 5 of your textbook, pages 135-162.
I have not been getting many email messages making comments, asking for
hints, etc., on the course material.
In fact, most of you have never sent me one.
Please change that.
-
Monday February 12, 2001.
Graduate Assignment 1
will be due on Monday, February 12, in class.
Students registered for CSC 656 are required to do this assignment.
We will spend some time reviewing material for the examination.
I do not expect to introduce the usual amount of new material today.
It looks like we made the
Las Vegas Sun, in the Tuesday, February 13 edition. The
article about graduate education in Nevada contains a link to a photo
showing two of our students: Dwain Seppala and Richard Sypert.
-
Wednesday February 14, 2001.
Homework due.
Assignment 4
will be due on Wednesday, February 14, in class.
Homework due.
Assignment 5
will be due on Wednesday, February 14, in class.
The reason that these two assignments are due the same day, is that you need
to work these to prepare for the examination. I would suggest that you
finish Assignment 4 by Monday.
Examination.
There will be an examination on Wednesday, February 14, in class.
This examination will cover material corresponding to the topics
up through Chapter 5 in your textbook.
-
Wednesday February 21, 2001.
Graduate Assignment 2
will be due on Wednesday, February 21, in class.
Students registered for CSC 656 are required to do this assignment.
There will be a modification to Graduate Assignment 2
because we have not covered PDA's yet.
I will no longer be able to hold afternoon office hours.
See new posted office hours.
See new posted office hours.
Today we will review some homework and exam questions.
If time permits, we will begin context-free languages
and pushdown automata, pages 161-336 of your textbook.
-
Monday February 26, 2001.
Today we will introduce context-free grammars.
Read pages 163-197 or your textbook.
-
Wednesday February 28, 2001.
Today we will continue the discussion of context-free grammars.
-
Monday March 5, 2001.
Assignment 6
will be due on Monday, March 5, in class.
Today we will continue the discussion of pushdown
automata and context-free languages.
Please read Chapters 6 and 7 of your textbook, pages 161-236,
by Wednesday.
-
Wednesday March 7, 2001.
Today we will continue the discussion of pushdown
automata and context-free languages.
We will discuss parsers today.
-
Monday March 19, 2001.
Assignment 7
will be due on Monday, March 19, in class.
Today we will begin the discussion of Turing machines,
which will dominate the remainder of the course.
The most important thing about Turing machines is that any computation
that can be done by any machine can be done by some Turing machine,
although perhaps by far more steps.
Thus, when we prove that a certain computation cannot be done by any
Turing machine, we have proved that no machine can do that compuation.
-
Wednesday March 21, 2001.
I must end office hours before 11:00 today, due to a faculty meeting
with the Regents' Consultants.
Today we will continue the discussion of Turing machines. We will
show how certain more complex machines can be emulated by Turing
machines.
-
Monday March 26, 2001.
Assignment 8
will be due on Monday, March 26, in class.
-
Wednesday March 28, 2001.
Examination.
There will be an examination on Wednesday, March 28, in class.
The examination will include material covered in classes up through
March 26.
-
Monday April 2, 2001.
Today we will continue the discussion of Turing machines. We will review
some concepts, and will explain how to combine simple Turing machines together
to form more complex Turing machines.
-
Wednesday April 4, 2001.
Today we will prove that some languages are undecidable.
-
Monday April 9, 2001.
I will hand back the graded exam today.
The exam grades are now available by email.
Be sure to include your student id number in your message, for verification
purposes. The median grade for the entire class is 75.
After reviewing the exam, we will continue the discussion of undecidability.
We will give a formal definition of reduction.
-
Wednesday April 11, 2001.
The most difficult concept of all in this course is the concept of an
NP-complete language (usually referred to as an
NP-complete problem.) Everyone talks about it, few
can even define it. After passing this course, you will be able to.
Some well-known NP-complete problems.
(Thousands are known.)
-
Monday April 16, 2001.
Today we will discuss NP-complete problems.
-
Wednesday April 18, 2001.
Assignment 9
will be due on Wednesday, April 18, in class.
Today, we will continue the discussion of NP-complete problems.
-
Monday April 23, 2001.
Today we will introduce the pumping lemma
for regular languages. We will then use that lemma to prove that
certain languages are not regular.
If time permits, we will introuce the pumping lemma
for context-free languages. We will then use that lemma to prove that
certain languages are not context-free.
-
Wednesday April 25, 2001.
Today we will complete the proof of the pumping lemma for
context-free languages. We will then give a polynomial time
algorithm, the CYK algorithm for decision for a context-free languages.
-
Monday April 30, 2001.
Today we will discuss the CYK algorithm again.
Detailed description of the CYK algorithm.
We will also give an outline of the proof of undecidability of the
grammar equivalence problem.
-
Wednesday May 2, 2001.
Today I will prove that there are some truths that are unprovable.
One question you might ask is, what is the meaning of "truth"? How
can you say that something is "true if there is no proof of it?
I will go over some specific problems. Here's one:
if L = {anbncn}, then L is not a
context-free language. But, the complement of L is context-free.
-
Wednesday May 9, 2001.
Final Examination at 6:00 PM. Two hours.
-
Final Grades are now ready.
You may email a request for your grade. Be sure to write "CSC456" or
"CSC656" in the subject field. For identification purposes,
please include your student ID number in the message.

Back to
Course Page