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

Examination.

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

Examination.

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.