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

-
-
Turning in Homework during the Covid Crisis
-
Your answers must be written in a pdf file and emailed to the graduate
assistant, Shekhar Singh
shekhar.singh@unlv.edu
by the posted time on the due date.
Your file must not exceed 5 megabyes, and must print out to at most 4 pages.
Monday, August 24, 2020
-
Welcome!
If you have registration issues today, see me right after class.
-
Wednesday, August 26, 2020
-
Reading Assignment
Read and study:
-
Section 1.2, Three Basic Concpts, which begins on page 26 of the fifth edition.
-
Section 1.3. Some Applications
-
Chapter 3, which ends on page 103 of the fifth edition.
Today, I will cover some of that material, including a review of everything
I presented on Monday. I will also cover all the meterial you need to work
Assignment 1.
-
-
Wednesday, September 2, 2020
-
-
-
-
Thursday, September 3, 2020
-
Turn in
Assignment 1 electronically by 23:59 today.
-
-
-
Monday, September 7, 2020
-
-
-
Wednesday, September 9, 2020
-
Practice Exam
-
-
-
Thursday, September 10, 2020
-
Be sure to login to my Zoom office hour today.
-
-
-
Saturday, September 12, 2020
-
-
Answers to Practice Exam
-
-
Monday, September 14, 2020
-
Examination today
-
-
-
280 Possible
-
183 Average
-
160 25 %-ile
-
208 50 %-ile (median)
-
215 75 %-ile
-
258 Highest
-
-
Wednesday, September 18, 2020
-
-
-
Monday, September 21, 2020
-
Enumeration.
-
Enumerable, recursively enumerable, canonical order of a language.
-
Every language is enumerable. Every acceptable language is recursively
enumerable. Every decidable language is recursively enumerable in canonical
order.
-
-
Wednesday, September 23, 2020
-
-
-
-
Thursday, September 24, 2020
-
-
-
-
Friday, September 25, 2020
-
Assignment 2 electronically by 23:59 today.
Finished now
-
Here are
Answers to a homework assignment from last semester
which will help you understand how to draw the diagram for a PDA.
-
There is an error in the diagram for probllem 2.
The self loop at state 0 shoulw have 6 labels instead of 2. I cannot seem
to get it loaded properly. I haven't figured out what's wrong.
-
-
Monday, September 28, 2020
-
Some True False Questions
-
These true false questions involve material we have covered in class up to now.
The list will be updated before the examination.
-
(i),(ii),(iii),(iv),(v),((vi),(vii),(viii),(ix),(x),(xi),(xii),(xiii),
(xvii),(xviii),
(xxxii)
,(xxxiv),(xliv),(xlv),(xlvii),(xlviii),(li),(liii),(liv),
(lv),(lvi),(lviii),(lix).
(xiv),(xv),(xvi),(xix),(xix),(xx),(xxiii),(xxvii),(xxix),(xxxvii),
(xxxix),(xliii),(xlvi),(lii),(lxii).
-
Wednesday, September 30, 2020
-
-
-
-
Friday, October 2, 2020
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
No one joined yesterday, although I know some students tried to get in.
Sorry abou that, I'll try to fix it.
-
-
Monday, October 5, 2020
-
Answers to Practice Exam
Finished
Corrected 5pm October 6
-
-
Tuesday, October 6, 2020
-
Office hour today 3-5. You will get an invitation on canvas, as usual.
-
-
Wednesday, October 7, 2020
-
Examination today
-
Practice Exam 2 Ready
I might add another problem.
-
-
Average 171
-
25 %-ile 145
-
50 %-ile 180
-
75 %-ile 200
-
highest 255
-
-
-
Monday, October 12, 2020
-
-
-
-
Wednesday, October 14, 2020
-
I have told you during lecture that SAT is NP-complete, as proved by the
Cook-Levin theorem. I also mentioned
that I will not give the proof, which is strightforward, but quite detailed
and difficult to grasp. However, you can read the proof on the internet.
Cook-Levin theorem: SAT is NP-complete.
-
I have told you that there is a P-time reduction of SAT to 3-SAT. Since
3-SAT is clearly NP, that proves that 3-SAT in NP-complete.
I have not yet (and might not ever) give you that reduction in lecture,
but here it is.
Reduction of SAT to 3-SAT
-
Today I gave a polynomial time reduction of 3-SAT to the independent set
problem. Since the independent set problem is NP, and since 3-SAT is
NP-complete, the independent set problem is NP-complete.
Here is a pdf document summarizing that proof.
-
Reduction of 3-SAT
to the independent set problem.
Today I gave the reduction of the independent set problem to the subset sum
problem. The subset sum problem is (trivially) in the class NP.
Thus, since the independent set problem is NP-complete, the subset sum problem
is NP-complete. Here is a pdf document summarizing that proof.
-
Reduction of the independent set
problem to the subset sum problem.
-
Reduction of the subset sum
problem to the partition problem.
-
-
Thursday, October 15, 2020
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
-
-
-
Monday, October 19, 2020
-
Computational Classes for CS456
-
A Simple NC algorithm
-
Every regular language is NC
-
Wednesday, October 21, 2020
-
-
-
-
Thursday, October 22, 2020
-
-
Office hour today 3-5
-
-
Friday, October 23, 2020
-
Turn in Assignment 3 by midnight today.
-
Office hour today 3-5
-
Problem 3: Addition is NC
-
Monday, October 26, 2020
-
-
-
Wednesday, October 28, 2020
-
-
-
-
Thursday, October 29, 2020
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
-
-
-
Monday, November 2, 2020
-
-
-
Wednesday, November 4, 2020
-
-
-
-
Friday, November 6, 2020
-
Turn in Assignment 4 by midnight today.
-
Corrections: Sat Oct 31 10:56:03 PDT 2020
-
Condensed version.
All problems on one page.
-
Expanded version.
Each problem on a separate page, giving you room to write the answers.
-
Answers
-
Remarks on Problem 5. I came up with a proof, but it was sort of complicated,
so I searched the internet for a simpler proof that the dominating set problem
is $\calN\calP$-complete. At first all I found were proofs that MSC (the
minimum set cover problem) reduces to Dominating set, but I didn't give you
MSC in the list. Finally, I found a page that gives a reasonably simple proof
that one of the problems in my list reduces to Dominating set. Look for it!
-
Office hour today 3-5
-
By popular demand, I am postponing the due date
to Monday midnight.
-
-
Monday, November 9, 2020
-
Today I gave a polynomial time reduction of 3-SAT to the dominating set
problem. Since the dominating set problem is NP, and since 3-SAT is
NP-complete, the dominating set problem is NP-complete.
Here is a pdf document summarizing that proof.
-
Reduction of 3-SAT
to the dominating set problem.
-
Office hour today 3-5
-
Wednesday, November 11, is Veterans' Day, a holiday.
-
Thursday, November 14, 2020
-
-
Office hour today 3-5
-
-
Friday, November 15, 2020
-
-
Office hour today 3-5 New
-
-
Monday, November 16, 2020
-
Examination today
-
-
-
-
Possible 270
-
Average 170
-
25 %-ile 158
-
50 %-ile 185 (median)
-
75 %-ile 210
-
Highest 255
-
Practice for Test 3
-
Answers
Newly Corrected! Refresh your Browser!
-
Wednesday, November 18, 2020
-
-
-
-
-
Thursday, November 19, 2020
-
No office hour today.
-
-
-
-
Monday, November 23, 2020
-
Some simple LALR parsers.
-
Updated Nov 30 15:32:03
-
-
GOTO Table of Example 1 Corrected November 27
-
Wednesday, November 25, 2020
-
-
-
-
Thursday, November 26, 2020
-
No office hour today because of the Thanksgiving holiday.
-
-
-
Friday, November 27, 2020
-
I plan to hold a Zoom office hour today from 4pm to 5pm,
even though, technically, we are still in the Thanskgiving recess.
-
-
Saturday, November 28, 2020
-
-
I plan to hold a Zoom office hour today from 4pm to 5pm.
-
Monday, November 30, 2020
-
Turn in Assignment 5
by 23:59 tonight
-
Answers to Assignment 5
Updated Dec 2 11:02
-
Corrected
-
I plan to hold a Zoom office hour today from 4pm to 5pm.
-
-
Wednesday, December 2, 2020
-
Turn in Assignment 6
by 23:59 tonight
-
Corrected
-
Consider Assignment 6 to be ``extra credit," meaning that if you haven't
mastered the previous topics in the course, skip it.
-
-
-
Thursday, December 3, 2020
-
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
-
Friday, December 4, 2020
-
ABET Assessment Test
-
The Accreditation Board of Engineering and Technology (ABET)
requires that we give an assessment test in each required course
for the Bachelor of Science degree in Computer Science.
Print out the above file, answer the questions, and email
a scanned copy to the TA. Do not write your name on the paper.
The requirement applies only to 456 students, not 656.
-
-
Wednesday, December 9, 2020
-
-
Final Examination 10:10 - 12:10
-
Practice Final
-
Updated Nov 30 15:01:59
-
Answers to Practice Final
-
Corrected Sat Dec 5 13:40:13 PST 2020
-
A Lot of True/False Questions
-
Be sure to also look at true/false questions on the three previous tests.

Back to
Course Page