University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Course Page
Computer Science 456/656
Automata and Formal Languages
Spring 2015
Assignments and Lecture Topics
Revised April 21, 2015

-
Tuesday, January 20, 2015
-
Today we will overview the course.
The two most important key words of the course are
language and computable.
We will start by discussing languages.
-
English, Spanish, Chinese, and other
natural languages, are not part of this course.
Programming languages are, however.
-
We will introduce deterministic finite automata (DFAs)
and regular languages.
-
Thursday, January 22, 2015
-
Today we will discuss the operations of union,
concatenation, and Kleene closure on languages.
The class of regular languages is
closed under those three operations.
-
We will introduce regular expressions and
non-deterministic finite automata (NFAs).
-
We state the Equivalence Theorem of Kleene, Rabin, and Scott.
-
Tuesday, January 27, 2015
-
Turn in Assignment 1 at the beginning of class today.
-
Today, I will go through the algorithm for minimizing a DFA.
-
Thursday, January 29, 2015
-
Today we will finish up regular languages.
-
We will discuss the pumping lemma.
-
If there is time, we will move on to
context-free grammars and languages.
-
Tuesday, February 3, 2015
-
We will begin the discussion of
context-free grammars and languages.
-
Thursday, February 5, 2015
-
Turn in Assignment 2 at the beginning of class today.
-
Tuesday, February 17, 2015
-
Turn in Assignment 3 at the beginning of class today.
-
Thursday, February 19, 2015
-
Turn in Assignment 4 at the beginning of class today.
-
Spring 2013 practice examination in pdf form
-
Spring 2013 practice examination in postscript form
-
I will not give any problem on any test that requires lectures that have not
yet been given. For example, as of Tuesday, February 17, we have not
covered LALR parsing. Thus, if we do not cover LALR parsing on
Tuesday, Februay 19, there will be
no problem similar to Problem 14 on the Spring 2013 practice exam.
If you have any concerns about whether something will be on the exam,
ask me in class or send me email.
-
First exam, Fall 2007:
in postscript form pdf form
-
First exam, Fall 2008:
in postscript form
pdf form
-
First exam, Spring 2009:
in
postscript form
pdf form
-
First exam, Fall 2010:
in
postscript form
pdf form
-
Possible score: 240
Highest score: 215
75 percentile score: 164
Median score: 150
25 percentile score: 122
Mean score: 145
-
Tuesday March 3, 2015.
-
Turn in Assignment 5 at the beginning of class today.
Corrected version: Fri Feb 27 05:12:31 PST 2015
-
This assignment deals with Converting an NFA to a minimal DFA.
-
Thursday March 5, 2015.
-
Turn in Assignment 6 at the beginning of class today.
For some reason, some students got the impression that, for problem 1,
they were required to prove that L is not context-free. That is not true.
I planned to do that proof Tuesday, March 3, but didn't get to it.
-
-
Tuesday March 10, 2015.
-
Thursday March 12, 2015.
-
Turn in Assignment 7 at the beginning of class today.
-
This assignment deals with LALR parsing.
-
Tuesday March 17, 2015.
-
Thursday March 19, 2015.
-
Tuesday March 24, 2015.
-
Turn in Assignment 8 at the beginning of class today.
-
Thursday March 26, 2015.
-
Assignment 9 has been postponed.
-
Tuesday April 7, 2015.
-
Thursday April 9, 2015.
-
Turn in Assignment 9 at the beginning of class today.
-
Tuesday April 14, 2015.
-
Turn in Assignment 10 at the beginning of class today.
-
Thursday, April 16, 2015
-
Examination today.
-
Second exam, Fall 2007:
in
postscript form
pdf form
-
Second exam, Fall 2008:
in
postscript form
pdf form
-
Second exam, Spring 2009:
in
postscript form
pdf form
-
Second exam, Fall 2010:
in
postscript form
pdf form
-
Possible score: 280
Highest score: 280
75 percentile score: 218
Median score: 189
25 percentile score: 171
Mean score: 193
-
Tuesday April 23, 2015.
-
Reduction of the Independent Set Problem to the Knapsack Problem
Being repaired. Thank you for your patience.
/a>
-
Tuesday April 30, 2015.
-
Turn in Assignment 11 at the beginning of class today.
-
Tuesday, May 12, 2015
- Final Examination, 6:00 to 8:00.
-
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.

Back to
Course Page