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
Fall 2018
Assignments and Lecture Topics

Revised December 10, 2018

Monday, August 27, 2018
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.
Wednesday, August 29, 2018
Today, and over the next few days, 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 non-deterministic finite automata (NFAs).
We will introduce regular expressions.
We state the Equivalence Theorem of Kleene, Rabin, and Scott.
We give the algorithm for minimizing a DFA.
We give the algorithm for finding a DFA equivalent to a given NFA.
Wednesday, September 5, 2018
Turn in Assignment 1 at the beginning of class today.
Tuesday, September 11, 2018
Important! Since yesterday morning, I have been unable to edit my web pages from home since both faculty.egr.unlv.edu and student.egr.unlv.edu are down. I can still edit those pages from my office, and you can still view them. They're working to fix the problem, but it might take a while.
Friday, September 14, 2018
I will be holding extra office hours today starting aroud 8:00 AM and ending sometime before noon.
The problem was fixed. I can now edit my web pages.
Monday, September 17, 2018
Turn in Assignment 2 at the beginning of class today.
I will be holding extra office hours today starting at 2:30 PM and ending at perhaps 2:45.
Wednesday, September 19, 2018
Examination today.
Friday, September 21, 2018
The examination is graded.
Possible Score: 175
25 percentile score: 75
50 percentile score: 100
75 percentile score: 120
Average score: 98
Highest score: 160
Wednesday, October 3, 2018
Turn in Assignment 3 at the beginning of class today.
Action and Goto Tables for the simple grammar
Monday, October 15, 2018
Work in Assignment 4 before the beginning of class today and bring it to class, but do not hand it in.
An ambiguous context free grammar for a more general algebraic language
Wednesday, October 17, 2018
Examination today.
Practice Exam
The Pumping Lemmata
Error Corrected on October 27, 2018
Sunday, October 21, 2018
The examination is graded.
Possible Score: 250
25 percentile score: 105
50 percentile score: 170
75 percentile score: 200
Average score: 155
Highest score: 235
Wednesday, October 31, 2018
Turn in Assignment 5 at the beginning of class today.
Wednesday, November 7, 2018
Turn in Assignment 6 at the beginning of class today. Corrected.
Tuesday, November 13, 2018
I will be in my office today from 10:45 to 1:00
Wednesday, November 14, 2018
Examination today.
Practice Exam
You should also study the problems listed in Assignment 6.
There are duplications.
Friday, November 16, 2018
The examination is graded.
Possible Score: 325
25 percentile score: 205
50 percentile score: 257
75 percentile score: 280
Average score: 240
Highest score: 295
Wednesday, November 28, 2018
Due to an emergency, I will not hold office hours from 1:00 to 2:00 today. I will be in my office from 10:00 to 11:00 as usual.
Read These notes.
Turn in Assignment 7 at the beginning of class today.
Several examples of unrestricted grammars.
A very good source of problems and explanations on a Finnish website In particular, look at the slides for pages 134-171.
Thursday, December 6, 2018
I will hold office hours today from 8:30 to 11:15 and from 1:00 to 2:00.
It is now 12:10 and the faculty meeting is over. I'll be in my office until 2:00.
No one showed up during the morning. If no one shows up in the afternoon, I will conclude that going out of my way to help you is pointless, and so I won't hold any office hours during finals week.

Someone did come in the afternoon, so I will hold office hours on Monday.
Monday, December 10, 2018
I will hold office hours today from 8:45 to to 1:00. If someone comes, I might hold office hours tomorrow at the same time.
Tuesday, December 11, 2018
I might hold office hours today from 8:30 to 1:00.
I don't want to come if no one needs my help, so if you're planning to show up, send me email.
Wednesday, December 12, 2018
Final Examination. 10:10 to 12:10.
Practice Exam
Problems 34 and 35 on the practice final
Corresponding proofs for the recursive case
Wednesday, January 23, 2019
I will be teaching CS 477 8:30 -- 9:45 MW and CS 456 11:30 -- 12:45 MW during the Spring 2019 Sememster.

Back to Course Page