Lectures: MW 10:00 - 11:15, ??? College Center
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 Friday, December 9, 9:00 AM.
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: September 26, October 3, October 5, and October 17, Monday, Monday, Wednesday, and Monday, respectively, are Jewish holidays. Instead of lecture, there will either be a zoom lecture, a recorded video lecture, or a quiz. I will announce details in class.
Video Links:
Brilliant
Video About Decidability 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 |
| 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 |