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