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

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

Revised January 20, 2020 XXX

Tuesday, January 21, 2020 XXX
Welcome! If you have registration issues today, see me right after class.
Today, we will talk about the most fundamental concepts of automata theory.
  1. symbol
  2. alphabet
  3. string
  4. language
  5. machine
Thursday, January 23, 2019
A copy of the exercises missing from the sixth edition
Oops, I was wrong! Problems 1-12 on pages 23-24 of the fifth edition are problems 9,10,11,12,6,13,14,15,16,17,18,7 on pages 14-15 of the sixth edition.
Problems 1-4, 7, 8 on pages 37-38 of the fifth edition are problems 2-5, 8,9 on page 28 of the sixth edition.

Thursday, January 30, 2019
I need to lecture some more before you turn in Assignment 2, so I have postponed it till next Tuesday.

Tuesday, February 4, 2020 XXX
Turn in Assignment 2 at the beginning of class today.

Thursday, February 11, 2020 XXX

Thursday, February 11, 2020 XXX
If you have any complaints about the grading of homework, please see the TA, Shekhar Singh, during his office hours, 11:00 - 1:00 tomorrow, Friday.

Tuesday, February 18, 2020 XXX
Examination today.
In preparation for the examination:
  1. Review the homework assignments.
  2. Work These problems
Answers to First Examination

Thursday, February 20, 2020 XXX
Read this! As many times as necessary until you understand it!

Tuesday, February 25, 2020 XXX
Examples of finding an equivalent regular expression

Thursday, February 27, 2020 XXX

Tuesday, March 3, 2020 XXX
Turn in Assignment 3 at the beginning of class today.

Thursday, March 5, 2020 XXX

Tuesday, March 10, 2020 XXX
Turn in Assignment 4 at the beginning of class today.
No changes, but some clues added Thu Oct 3 17:44:12 PDT 2020

Thursday, March 12, 2020 XXX
Examination today.
In preparation for the exam. review all homeork assignments.
Answers to Assignment 1 Updated December 8
Answers to Assignment 2 Updated December 8
Answers to Assignment 3 Updated December 8
Answers to Assignment 4 Updated December 8
In preparation for the exam, try to answer these questions.
Some of the questions deal with material we have not covered; however, on the examination, all questions will deal with meterial we will have covered by that time.
Answers to Second Examination

Tuesday, March 24, 2020 XXX

Thursday, March 26, 2020 XXX

Tuesday, March 31, 2020 XXX
Turn in Assignment 5 at the beginning of class today.
Updated March 17

Thursday, April 2, 2020 XXX
The halting problem is undecidable Read this! Typos corrected: Tue Oct 29 17:45:56 PDT 2020>

Tuesday, April 7, 2020 XXX
3SAT is NP-complete Typos corrected: Wed Oct 30 06:06:46 PDT 2020
Independent Set is NP-complete Read this! Typos corrected: Tue Oct 29 17:45:56 PDT 2020>
Subset Sum is NP-complete

Thursday, April 9, 2020 XXX
The Cook-Levin Theorem: SAT is NP-complete
Partition is NP-complete

Tuesday, April 14, 2020 XXX
NC Addition

Thursday, April 16, 2020 XXX
A General Grammar Example Error Corrected Nov 12
The Pumping Lemmas X

Tuesday, April 21, 2020 XXX
Turn in Assignments 6 and 7 at the beginning of class today.

Thursday, April 23, 2020 XXX
Examination today.
In preparation for the exam. review all homeork assignments.
Answers to Assignment 5 Updated December 8
Answers to Assignments 6 and 7
The test will contain both of the following:
  1. Prove that Partition is NP-complete, using the fact that Subset Sum is NP-complete.
  2. Prove that the halting problem is undecidable.
Answers to Third Examination

Tuesday, April 30, 2020 XXX

Thursday, May 2, 2020 XXX

Tuesday, May 7, 2020 XXX

Thursday, May 9, 2020 XXX

Thursday, May 14, 2020 XXX
Assignment 8
Answers to Assignment 8

Thursday, May 16, 2020
I will hold office hours today, 10:00 to 11:00 and 1:00 to 2:00.

Back to Course Page