Theory of Computation Detailed Syllabus for Computer Science and Engineering M.Tech first year second sem is covered here. This gives the details about credits, number of hours and other details along with reference books for the course.
The detailed syllabus for Theory of Computation M.Tech 2017-2018 (R17) first year second sem is as follows.
M.Tech. I Year II Sem.
Course Outcomes
- Able to understand the concept of abstract machines and their power to recognize the languages.
- Able to employ finite state machines for modeling and solving computing problems.
- Able to design context free grammars for formal languages.
- Able to distinguish between decidability and undecidability.
- Able to gain proficiency with mathematical tools and formal methods.
UNIT – I: Regular Languages –Finite Automata, Formal definition of finite automaton, Examples of finite automata, Formal definition of computation, Designing finite automata, The regular operations, Non determinism, formal definition of nondeterministic finite automaton, equivalence of NFAs and DFAs, closure under the regular operations, Regular Expressions, formal definition of a regular expression, equivalence with finite automata, Nonregular languages, The pumping lemma for regular languages.
UNIT – II : Context-Free languages, Context-free grammars, formal definition of a Context-free grammar, Examples of context-free grammars, Designing context-free grammars, Ambiguity, Chomsky normal form, Pushdown Automata, Examples of pushdown Automata, Equivalence with context-free grammars, Non-context-free languages, The pumping lemma for context-free languages.
UNIT – III : The Church-Turing Thesis – Turing machines, Formal definition of turing machine, Examples of turing machines, Variants of turing machines, Multitape turing machines, Nondeterministic turing machine, Enumerators, Equivalence with other models, The definition of algorithm, Hilbert’s problem Terminology of describing turing machines.
UNIT – IV: Decidability – Decidable languages, Decidable problems concerning regular languages, Decidable problems concerning context-free languages, The halting problem, The diagonalization method, The halting method is undecidable, A turing –unrecognizable language, Reducibility – Undecidable problems for language theory, Reductions via computations histories, A simple undecidable problem, Mapping reducibility, computable functions, Formal definition of mapping reducibility.
UNIT – V: Time Complexity – Measuring complexity, Big – O and small-o notation, Analyzing algorithms, Complexity relationships among models, The class P, Polynomial time, examples of problems in P, The class NP, Examples of problems in NP, The P versus NP question, NP-Completeness, polynomial time reducibility, Definition of NP-Completeness, The Cook-Levin Theorem, Additional NP Complete problems, The vertex cover problem, The Hamiltonian path problem, The subset sum problem.
TEXTBOOKS:
- Introduction to the theory of computation, Micheal Sipser, Third Edition, Cengage Learning.
REFERENCES:
- Introduction to Languages and The Theory of Computation, John C Martin, TMH.
- Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.
- A Text book on Automata Theory, P. K. Srimani, Nasir S. F. B, Cambridge University Press.
- Introduction to Formal languages Automata Theory and Computation Kamala Krithivasan, Rama R, Pearson.
- Theory of Computer Science – Automata languages and computation, Mishra and Chandrashekaran, 2nd edition, PHI.
For all other M.Tech 1st Year 2nd Sem syllabus go to JNTUH M.Tech Computer Science and Engineering 1st Year 2nd Sem Course Structure for (R17) Batch.
All details and yearly new syllabus will be updated here time to time. Subscribe, like us on facebook and follow us on google plus for all updates.
Do share with friends and in case of questions please feel free drop a comment.