Theory of Computation

Paper Code: 
MCA 525F
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 

·         To understand the basic concept, approaches and techniques of TOC

·         To develop a deeper understanding of automata and grammar.

To develop the basic skills necessary to deal with unsolvable problems.

12.00
Unit I: 

Review of basic concepts

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. 

12.00
Unit II: 

Finite Automata

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. 

12.00
Unit III: 

Grammar

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).

 

12.00
Unit IV: 

Turing Machines and Computability Theory

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.

12.00
Unit V: 

Unsolvable Problems and Computable Functions                       

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.

ESSENTIAL READINGS: 

·         John C. Martin, “Introduction to Languages and the Theory of Computation”, McGraw-Hill, 2003 

Michael Sipser, “Introduction to the Theory of Computation”, Cengage Publication, 2003 

REFERENCES: 

Wayne Goddard, “Introducing the Theory of Computation”, Jones & Bartlett India Pvt.Ltd, 2009.

Academic Year: 
2016-17
  • Printer-friendly version