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

Revised May 21, 2014

Tuesday, January 21, 2014

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 23, 2014

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 and non-deterministic finite automata (NFAs).

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

Tuesday, January 28, 2014

Turn in Assignment 1 at the beginning of class today.

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

Thursday, January 30, 2014

Today we will finish up regular languages.

We will discuss the pumping lemma.

If there is time, we will move on to context-free grammars and languages.

Tuesday, February 4, 2014

Turn in Assignment 2 at the beginning of class today.

We will begin the discussion of context-free grammars and languages.

Thursday, February 6, 2014

We will continue our discussion of context-free grammars and languages.

Tuesday, February 11, 2014

Turn in Assignment 3 at the beginning of class today.

Thursday, February 13, 2014

Today, we will show how to design a PDA which accepts a context-free language. In fact, we will learn two such designs: one is top-down, the other bottom-up. Neither construction is deterministic.

If time permits, we will also give the CYK algorithm for the membership problem of a context-free language.
Or maybe it's called the "CKY" algorithm. I can never remember.

Tuesday, February 18, 2014

Turn in Assignment 4 at the beginning of class today.

Thursday, February 20, 2014

Examination today.

Spring 2013 practice examination in pdf form

Spring 2013 practice examination in postscript form

We have not covered LALR parsing, and thus, the exam will contain no problem similar to Problem 14 on the Spring 2013 practice exam.

First exam, Fall 2007: in 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

Possible score:
Highest score: 211
75 percentile score: 158
Median score: 140
25 percentile score: 115
Mean score: 145

Tuesday, February 25, 2014

Tuesday, March 4, 2014

Thursday, March 6, 2014

Turn in Assignment 5 at the beginning of class today.

Today we will begin the discussion of decidability and computability. We will start with a definition of a Turing machine.

Tuesday, March 11, 2014

Thursday, March 13, 2014

Turn in Assignment 6 at the beginning of class today.

Tuesday, March 25, 2014

Thursday, March 27, 2014

Tuesday, April 1, 2014

Turn in Assignment 7 at the beginning of class today.

Thursday, April 3, 2014

Tuesday, April 8, 2014

Turn in Assignment 8 at the beginning of class today.

Thursday, April 10, 2014

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

Possible: 260
Highest score: 245
75 percentile score: 195
Median score: 165
25 percentile score: 144
Mean score: 163

Tuesday, April 15, 2014

Thursday, April 17, 2014

Today I will refer to the fact that Boolean satisfiability, abbreviated SAT, is NP-Complete. We will use that result, called the Cook-Levin theorem henceforth, although I will not give a proof in class.

Also today, I will refer to the fact that 3-CNFSAT is NP-complete, and will use that result to prove that the independent set problem is NP-complete.

Tuesday, April 22, 2014

Thursday, April 24, 2014

A description of NP-completeness.

Handout in pdf form

Handout in postscript form

Tuesday, April 29, 2014

Thursday, May 1, 2014

Turn in Assignment 9 at the beginning of class today.

Tuesday, May 6, 2014

Thursday, May 8, 2014

Tuesday, May 13, 2014

Final Examination, 6:00 to 8:00.

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.

These practice finals are from previous semesters. They may contain questions on topics we did not cover this semester, and there may be topics we covered this semester that are not on these practice finals.

Wednesday, May 21, 2014

It's almost 2:00 AM, and I have posted the grades.