THEORY OF COMPUTATION

Paper Code: 
MIT 321
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 

This course is aimed to inculcating programming logic development skills in a student.

12.00
Unit I: 

Introduction to Set theory: Definition of sets and Subsets, Properties and operations, Type of Sets: Countability – Unaccountability sets, Relations and Functions, closure of relations, Type of functions: Primitive recursive and partial recursive functions, Computable and non computable functions. Fundamentals Formal representation of languages: Strings, Alphabet, grammar, Language, Operations, Chomsky Classification, languages and their relationships, Recursively enumerable set.

12.00
Unit II: 

Introduction to Automata theory: Definition of Automation ,Finite Automata, Formal definition, Language acceptability by Finite Automata, Transition Diagrams and Transition systems, Deterministic and Nondeterministic finite automation, Finite Automation with- Transitions, Mealy and Moore Models, Conversion of NFA to DFA –e-Transitions, Eliminating e Regular operations, Regular sets and Regular Expressions, Pumping lemma for regular languages, Applications of finite state automata :Lexical analyzers and Text search.

12.00
Unit III: 

Context free language: Derivation tree, Ambiguity in Context free grammar, Simplification of CFG, Normal Forms, Pumping lemma for Context free languages.

Pushdown Automata: Formal definition, Language acceptability by PDA, Deterministic and nondeterministic PDA, Context free grammar, Applications of PDA – Parsing.

12.00
Unit IV: 

Turing Machines: Formal definition, Language acceptability, Universal Turing Machines – Halting Problem of Turing Machines, Linear bounded automaton.

12.00
Unit V: 

Algorithm: definition of algorithm and decidability, Algorithmic complexity, Tractable and intractable problems, Church’s Thesis. , Complexity classes, Class P, Class NP, NP Complete and NP Hard problems.

ESSENTIAL READINGS: 
  1. Theory of Computer Science – K.L.P. Mishra, N. Chandrashekharan, Prentice Hall of India
REFERENCES: 

1. Introduction to the Theory of Computation- Michael Sipser, Brooks/Cole (Thomson Learning)

2. Elements of the theory of computation -Harry R Lewis, Christos H Papadimitriou Prentice Hall of India / Pearson Education Asia

3. The Theory of Computation – Bernard M Morct (Pearson Edn)

4. Introduction to Automata Theory, Languages & Computation John Hopcroft, Rajeev Motwani & Jeffry Ullman (Pearson Edn)

Academic Year: