**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

Assignment_1 | Assignment_2 | Assignment_3 | Assignment_4 |

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 |

4 | Closure Properties of Regular Sets - a constructive review. Encoding FSMs, diagonalization, and a non-regular set. |
4.1- 4.2 |

5 | The Pumping Lemma - How to show that a set is not Regular. |
4.3 |

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

7 | Context Free Languages: Context Free Grammars and Applications, Syntax Diagrams. |
6 |

8 | Pushdown Machines - Deterministic versus non-deterministic. |
7 |

9 | 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 |

11 | The CFL Pumping Lemma - Showing that a set is not context free. |
9.2 |

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 |