Published on Computer Science & IT (https://www.csit.iisuniv.ac.in)

Home > Theory of Computation

Theory of Computation [1]

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 [2]

Follow Computer Science & IT on:

IIS (Deemed to be University)

Gurukul Marg, SFS, Mansarovar, Jaipur 302020, (Raj.) India Phone:- +91-141-2400160-61, 2397906-07, Fax: 2395494, 2781158

Source URL: https://www.csit.iisuniv.ac.in/courses/subjects/theory-computation-8

Links:
[1] https://www.csit.iisuniv.ac.in/courses/subjects/theory-computation-8
[2] https://www.csit.iisuniv.ac.in/academic-year/2016-17