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

Revised May 8, 2016

Tuesday, January 19, 2016

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.

Thursday, January 21, 2016

We will instruduce non-deterministic finite automata (NFAs).

Today, I will go through the algorithm for minimizing a DFA.

Today, I will go through the algorithm for transforming an NFA to an equivalent DFA.

Tuesday, January 26, 2016

Turn in Assignment 1 at the beginning of class today.

Today 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 regular expressions.

We state the Equivalence Theorem of Kleene, Rabin, and Scott.

Tuesday, February 2, 2016

Turn in Assignment 2 at the beginning of class today.

Tuesday, February 9, 2016

Turn in Assignment 3 at the beginning of class today.

Tuesday, February 16, 2016

Turn in Assignment 4 at the beginning of class today.

Saturday, February 20, 2016

Some students have requested additional reading material on LALR parsing. That subject is quite complex, and you'll get a full treatment in CS460/660. Meanwhile, you can look at Dr. Pedersen's textbook. e/dd>

There is a very simple grammar given in Section 4.9.3, at the top of page 188 of the book. The action and goto tables are then given on page 193. An example computation is given at the top of page 194.

Another example, Example 4.25, is given at the top of page 202. Several pages are devoted to computing the stack states for this grammar, after which the action and goto tables are given on page 212.

Some more examples.

Tuesday, February 23, 2016

Examination today.

First exam, Fall 2007: n postscript form pdf form

First exam, Fall 2008: in postscript form pdf form

First exam, Spring 2009: in postscript form pdf form

First exam, Fall 2010: in postscript form pdf form

Spring 2013 practice examination: in postscript form pdf form

Possible score: 240
Highest score: 219
75 percentile score: 176
Median score: 138
25 percentile score: 115
Mean score: 144

Tuesday, March 1, 2016

Turn in Assignment 5 at the beginning of class today.

Tuesday, March 8, 2016

Turn in Assignment 6 at the beginning of class today. Assignment posted March 1.

Tuesday, March 15, 2016

Turn in Assignment 7 at the beginning of class today.

Thursday, March 17, 2016

Handout in pdf form

Handout in postscript form

Thursday, March 31, 2016

Turn in Assignment 8 at the beginning of class today.

I hope to have this assignment ready by March 19.

Clearly, my hope was ill-founded. Now, I hope to have it ready by tomorrow (Monday).

Finally, it's ready!

Thursday, April 7, 2016

Turn in Assignment 9 at the beginning of class today.

Thursday, April 14, 2016

Examination today.

I gave three exams during the Fall semester of 2013. Our exam on Thursday will somewhat overlap both the second and the third exams of Fall 2013.

Fall 2013 practice second examination in postscript form.

Fall 2013 practice second examination in pdf form.

This is the third examination of Fall 2013. On Thursday's test, I will not ask any question that deals with material we have not covered by that date.

Fall 2013 practice third examination in postscript form.

Fall 2013 practice third examination in pdf form.

I gave only two exams during the Spring semester of 2013. The following is much closer to what the exam on Thursday will be like. However, I won't give any question on the test that refers to material we haven't covered.

Spring 2013 practice examination in pdf form

Spring 2013 practice examination in postscript form

Thursday, April 21, 2016

No homework due today.

Thursday, April 28, 2016

Turn in Assignment 10 at the beginning of class today.

Thursday, May 5, 2016

There were supposed to be in-class student evaluations today. I plan to ask the chairman, Dr. Gewali, to do the evaluations at the beginning of the Final Exam. This will delay the start of the exam by about 10 minutes.

Tuesday, May 10, 2016

Final examination today at 6:00 PM.

Spring 2013 practice final in postscript form.

Spring 2013 practice final in pdf form.

Fall 2012 practice final in postscript form.

Fall 2012 practice final in pdf form.

Fall 2010 practice final in postscript form.

Fall 2010 practice final in pdf form.

Spring 2009 practice final in postscript form.

Spring 2009 practice final in pdf form.

Fall 2007 practice final in postscript form.

Fall 2007 practice final in pdf form.

Spring 2013 practice final in postscript form.