CSC 384 - Theory of Computation

Shai Simonson    306 Stanger    (508) 565-1008



Lectures:  MWF 10:30 - 11:20, 001 Stanger

Text:  Introducing the Theory of Computation  by Wayne Goddard,  Jones and Bartlett Publishers, 2009.

Description:  A theoretical treatment of what can be computed and how fast it can be done. Applications to compilers, string searching, and control circuit design will be discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines will be analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course.

Exams:  There will be six quizzes and I will count the best five (25%).  There is one final examination (35%).  The final will be TBA.

Assignments:  Homeworks are worth 40% of your grade.   You may do these with a partner, and one grade will be given to both people in each group.  Read our department's academic integrity guidelines before you hand in any written work.

Goals:  To appreciate computer science as a discipline with an elegant formal foundation with an uncanny number of practical applications.  To understand abstract computational models, write machine “programs” for each one, and prove theorems with regard to their power.  To appreciate and prove that some problems require more time and space for a computer solution, and some are undecidable.

Special Dates:  Mondays October 3, 17, and 24, and Wednesday October 12 are Jewish holidays. Instead of lecture, there will be a quiz or I will announce other plans in class.

Video Links:            Index of all ADUni Lectures         YouTube of my Theory Lectures

Handouts:               Syntax Diagrams for Pascal            Closure Properties of Regular Sets, CFLs, DCFLs, and other Languages           Old Class Notes    

Other Fun Links:   Alan Turing Page     Turing Award     Funny Halting Poem        Brzozowski's FSM Minimization Algorithm         

A Real Turing Machine        Halting Problem Video


Assignment_1 Assignment_2  Assignment_3 Assignment_4


Brief Syllabus

Week Topics Reading
1 Introduction:  Languages, Grammars, and Automata (Machines). Fundamental connection to computer science.  Applications.   5
2 Regular Sets:  Finite State Machines,  Regular Expressions, and Regular Grammars 1, 2, 8.1
3 Non-determinism and equivalence of NFSM's to DFSM's.  Other variants of FSM's 3
Closure Properties of Regular Sets - a constructive review.  Encoding FSMs, diagonalization, and a non-regular set.

4.1- 4.2
The Pumping Lemma - How to show that a set is not Regular.

Decision Algorithms for FSM's.  (Problems whose inputs are FSM's.)  Decidability.

Context Free Languages:  Context Free Grammars and Applications, Syntax Diagrams.

Pushdown Machines - Deterministic versus non-deterministic.

Chomsky Normal Form - Three applications.   Equivalence of NPDM and CFL's.

8, 9.1

Midterm -- or Quizzes every two weeks

10 Closure Properties of CFL's and DCFL's.  Decision Algorithms for CFL's.  Applications to compilers. 10.1, 10.2
The CFL Pumping Lemma - Showing that a set is not context free.

12 Turing Machines and Variants:  Multi-tape, non-determinism, multidimensional, 2-stack machines. 11, 12
13 Decidability:  The Halting Problem.  Reductions and more Undecidable problems:  Post's Correspondence Problem, CFL equivalence, CFL ambiguity. 13, 14, 15
14 Computational Complexity - Measuring the time and space requirements of decidable problems.

17, 18
15 The computational classes P and NP.  The concept of an NP-Complete Problems.  Reductions revisited.

17.6, 19