Theory of Computation

Graphs, Trees, Strings, Mathematical Induction, finite State Machine - types of languages and Grammars. Overview of Theoretical Computer Science (including computationally intractable problems) - Introduction to System software including various phases / modules in the design of a typical compiler - Chomsky Classification.

Introduction to formal proof – Additional forms of proof – Inductive proofs - Basic Mathematical Notation and techniques- Finite State systems – Basic Definitions – Finite Automaton – DFA & NDFA – Regular Languages- Regular Expression – Equivalence of NFA and DFA - Equivalence of finite Automaton and regular expressions –Minimization of DFA.

Introduction– Types of Grammar – Context Free Grammars and Languages– Derivations and Languages – Ambiguity- Relationship between derivation and derivation trees – Simplification of CFG – Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Equivalence of Pushdown automata and CFL - Pumping Lemma, Parsing ( including LL(1) , SLR and LR(1) Parsing Method).

Definition of Turing Machine, Extensions of Turing machines, Non – deterministic Turing machines, Equivalence of various Turing Machine Formalisms, Church – Turing Thesis, Decidability, Halting Problem, Reducibility, Recursion Theorem.

Unsolvable Problems and Computable Functions – Primitive recursive functions – Recursive and recursively enumerable languages – Universal Turing machine. Measuring and Classifying Complexity: Tractable and Intractable problems- Tractable and possibly intractable problems – P and NP completeness.