Lectures: MWF 10:30 - 11:20, 001 Stanger
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
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.
of all ADUni Lectures
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
Halting Poem Brzozowski's
FSM Minimization Algorithm
A Real Turing Machine Halting Problem Video
|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.
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.
|Midterm -- or Quizzes every
|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
|15||The computational classes P and
NP. The concept of an NP-Complete Problems.