University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
Deparment of Computer Science
My Home Page
Course Page
Computer Science 456/656
Automata and Formal Languages
Fall 2013
Assignments and Lecture Topics
Revised December 17, 2013

-
Tuesday September 3, 2013.
-
Oops! The DFA I drew on the board at the end of class today accepts the
language of all unary strings of odd length,
not even. Sorry!
-
Tuesday September 3, 2013.
-
Turn in Assignment 1 at the beginning of class today.
-
Tuesday September 10, 2013.
-
Turn in Assignment 2 at the beginning of class today.
-
Thursday, September 12, 2013
-
Examination Today.
-
Practice examination in postscript form.
-
Practice examination in pdf form.
-
Possible score: 190
Highest score: 188
75 percentile score: 150
Median score: 138
25 percentile score: 110
Mean score: 131
-
Tuesday September 24, 2013.
-
Turn in Assignment 3 at the beginning of class today.
-
Tuesday October 1, 2013.
-
Turn in Assignment 4 at the beginning of class today.
-
Thursday October 3, 2013.
-
Corrected handout from Tuesday in postscript form.
-
Corrected handout from Tuesday in pdf form.
-
Tuesday October 8, 2013.
-
Turn in Assignment 5 at the beginning of class today.
-
Thursday, October 10, 2013
-
Closure properties
-
Examination Today.
-
Practice examination in postscript form.
-
Practice examination in pdf form.
-
Possible score: 220
Highest score: 205
75 percentile score: 173
Median score: 161
25 percentile score: 138
Mean score: 156
-
Tuesday October 15, 2013.
-
This course basically falls into four parts, in increasing order of
hardness. We have already done the first two parts, regular languages
and context-free languages, including parsing.
-
The third part begins today, and deals with computability and decidability.
-
"Computable" means computable by a machine.
If you have taken some advanced mathematics course, you have learned that
every subset of a countable (i.e., enumerable) set is countable.
That statement is true, in the following sense: if there exists an enumeration
of an infinite set X, and if S is an infinite subset of X, then there exists an
enumeration of S.
But there is a big difference between "exists" and "computable."
If a set can be enumerated by a machine, we call it "recursively enumerable."
Not every set which is enumerable is recursively enumerable.
-
Tuesday October 22, 2013.
-
Turn in Assignment 6 at the beginning of class today.
Assignment 6 is canceled.
-
Tuesday October 29, 2013.
-
Turn in Assignment 7 at the beginning of class today.
-
Tuesday November 5, 2013.
-
Turn in Assignment 8 at the beginning of class today.
- Thursday, November 7, 2013
-
Examination Today.
-
Practice examination in postscript form.
-
Practice examination in pdf form.
-
I am not happy about the low scores on this test.
-
Possible score: 255
Highest score: 250
75 percentile score: 165
Median score: 140
25 percentile score: 110
Mean score: 144
-
Tuesday November 19, 2013.
-
A definition of NP-completeness,
using certificates.
-
The
Cook-Levin Theorem states that Boolean satisfiability
is NP-complete.
-
Thursday November 21, 2013.
-
Reduction of the independent set problem to the knapsack problem:
Portable document format.
Postscript format.
-
Tuesday November 26, 2013.
-
Turn in Assignment 9 at the beginning of class today.
-
What is a context-sensitive language?
-
postscript format
-
Tuesday, December 10, 2013
-
Final Examination today at 1:00 PM.
-
Spring 2013 practice final in postscript form.
-
Spring 2013 practice final in pdf form.
-
Fall 2012 practice final in postscript form.
-
Fall 2012 practice final in pdf form.
-
Fall 2010 practice final in postscript form.
-
Fall 2010 practice final in pdf form.
-
Spring 2009 practice final in postscript form.
-
Spring 2009 practice final in pdf form.
-
Fall 2007 practice final in postscript form.
-
Fall 2007 practice final in pdf form.
-
These practice finals are from previous semesters.
They may contain questions on topics we did not cover this semester,
and there may be topics we covered this semester that are not on these
practice finals.
-
Tuesday, December 17, 2013.
-
I have submitted the grades, finally.

Back to
Course Page
