University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

Computer Science 456/656
Automata and Formal Languages Spring 2019
Assignments and Lecture Topics

Revised May 13, 2019

Wednesday, January 23, 2019
We will begin with some basic definitions.
Wednesday, January 30, 2019
Turn in Assignment 1 at the beginning of class today.
Tuesday, February 5, 2019
I have good news for people on the waiting list who've been coming to class in hopes of getting in.
Wednesday, February 6, 2019
Turn in Assignment 2 at the beginning of class today.
(0+1+ε) (0+1+ε) (0+1+ε) +(1+00+011+0100+0101(0+1))(0+1)* is a regular expression for the language over {0,1} consisting of all strings except 0101.
Monday, February 11, 2019
Practice Exam
180 Possible Score
175 Highest Score
140 75%ile Score
120 50%ile Score (median)
97 25%ile Score
119 Average Score

Wednesday, February 20, 2019
Turn in Assignment 3 at the beginning of class today.
Wednesday, March 6, 2019
Turn in Assignment 4 at the beginning of class today.
There are questions on this homework where you will need to look up the answers. But there is nothing you can't easily find.
Monday, March 11, 2019
Examination today. Study guide.
215 Possible Score
210 Highest Score
160 75%ile Score
125 50%ile Score (median)
95 25%ile Score
129 Average Score
Monday, March 18, 2019
Spring break begins today. No class.
Monday, March 25, 2019
Classes resume.
Monday, April 1, 2019
Turn in Assignment 5 at the beginning of class today.
Monday, April 8, 2019
Turn in Assignment 6 at the beginning of class today.
Homework has been updated. There are no additional problems.
Tuesday, April 9, 2019
I have found that the context-free grammar membership problem is P-complete. That means, it is not in NC unless P = NC. I was mistaken when I told the class that that problem is in NC.
Monday, April 15, 2019
Practice Exam . Ready now.
295 Possible Score
290 Highest Score
260 75%ile Score
230 50%ile Score (median)
200 25%ile Score
226 Average Score

Monday, April 22, 2019
The DFA acceptance problem is in NC
Various reductions to prove NP-completeness
Tuesday, May 14, 2019
I will be in my office most of the morning. I might have to take time to meet a faculty candidate.
Wednesday, May 15, 2019
Final Examination. 10:10 to 12:10.
Practice Exam
Answers to Practice Exam.
Updated: I have fixed all the errors I found. Mon May 13 18:48:43 PDT 2019
Please check for errors. If you find any, send me email immediately!
If you have any questions about the final examination, do not hesitate to contact me by email.

Back to Course Page