Theory of Computing detailed syllabus scheme for B.Tech Information Technology (IT), 2017 onwards has been taken from the DBATU official website and presented for the Bachelor of Technology students. For Subject Code, Course Title, Lecutres, Tutorials, Practice, Credits, and other information, do visit full semester subjects post given below.
For all other DBATU Syllabus for Information Technology 6th Sem 2017, do visit IT 6th Sem 2017 Onwards Scheme. The detailed syllabus scheme for theory of computing is as follows.
Theory of Computing Syllabus for Information Technology (IT) 3rd Year 6th Sem 2017 DBATU
Course Objectives:
For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdf platform to make students’s lives easier.
.
Course Outcomes:
After learning the course the students should be able:
- Design Finite State Machine, Pushdown Automata, and Turing Machine.
- Explain the Decidability or Undecidability of various problems
Unit I
Fundamentals: Strings, Alphabet, Language, Operations, Finite state machine, Definitions, Finite automaton model, Acceptance of strings and languages, Deterministic finite automaton and Non deterministic finite automaton, Transition diagrams, Language recognizers.
Unit II
For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdf platform to make students’s lives easier..
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 -Elimination of Useless symbols – Unit productions – Null productions – Greiback Normal form – Chomsky normal form – Problems related to CNF and GNF
Unit IV
Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata -Equivalence of Pushdown automata and CFL – pumping lemma for CFL – problems based on pumping Lemma.
Unit V
For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdf platform to make students’s lives easier..
Unit VI
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 – Polynomial time reductions.
Text Books:
- Hopcroft J. E., Motwani R. and Ullman J. D., Introduction to Automata Theory, Languages and Computations, Second Edition, Pearson Education, 2008.
- John C Martin, Introduction to Languages and the Theory of Computation, Tata McGraw Hill Publishing Company, New Delhi, Third Edition, 2007.
Reference Book:
- Mishra K L. P. and Chandrasekaran N, Theory of Computer Science – Automata, Languages and Computation, Third Edition, Prentice Hall of India, 2004.
- Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Second Edition, Prentice Hall of India, Pearson Education, New Delhi, 2003.
- Peter Linz, An Introduction to Formal Language and Automata, 3rd edition, Narosa Publishers, New Delhi, 2002.
- Kamala Krithivasan and Rama R., Introduction to Formal Languages, Automata Theory and Computation, Pearson Education, 2009.
For detail syllabus of all other subjects of Information Technology (IT) 6th Sem 2017 regulation, visit IT 6th Sem Subjects syllabus for 2017 regulation.