Theory of Computation
 

Course Plan

Module I  Introduction to formal proof – Inductive proofs – Concepts of automata theory (  m1tc-1.pdf )

Deterministic finite automata – Nondeterministic finite Automata – equivalence of DFA and NFA – NFA with  ε transitions. Regular expressions – Finite automata and regular expressions – Algebraic laws for Regular expressions. Pumping lemma for regular languages – closure properties of regular languages.  Decision properties of regular languages.  ( m1tc-2.pdf  )

 Equivalence and minimization of automata

Mandatory notes if you are not bringing the other materials (  m1tc-mandat.pdf   )

Module II  Context free Grammars – Derivations – sentential forms – The language of grammar – Parse trees – Ambiguity in grammar and languages – Inherently ambiguous languages – Pushdown automata – Formal definition – Graphical notation (  pda-1.pdf  )

 The language of a PDA – Acceptance by PDA – Empty stack – Final state – PDAs to grammars – Deterministic PDAs and CFLs – Non deterministic PDAs (  pda-2.pdf  )

 Chomsky Normal Form – Greibach Normal Form ( cfg-normalforms.pdf   )

Pumping lemma for CFLs  ( cfg-pumpingLemma.pdf  )

Closure properties of CFLs – Decision properties of CFLs – CYK algorithm

 

Module III  Turing Machines – Notation – Instantaneous Description – Transition Diagram – The language of a Turing Machine  (  tm1.pdf  )

 Halting of TMs – Programming techniques for Turing Machines – Extension to basic TMs – Nondeterministic TMs – Restricted TMs – Recursive and Recursively Enumerable Languages – Halting problem of TMs – Undecidable problem about TMs   (   tm2.pdf   )

Rice's Theorem – Post's Correspondence problem – Undecidablity of PCP – Undecidable problems on Languages

 

Module IV Intractable problems – The classes P and NP – Polynomial time reducibility – NP-Complete problems – The Satisfiability problem – NP-Completeness of the satisfiability problem  (  tc-m4-1.doc   )

 NP-Completeness of CSAT – NP-Completeness of 3SAT – Node cover problem – Directed Hamiltonian circuit problem – The class of languages Co-NP – Problems solvable in polynomial space.

 
References

Hopcroft J.E, Motwani R & Ullman J. D., Introduction to Automata Theory, Languages and Computation, Pearson Education.

 Assignment Questions : assigntqns1.doc