Theory of Computation detailed syllabus for Computer Science & Engineering (CSE) for 2021 regulation curriculum has been taken from the Anna University official website and presented for the CSE students. For course code, course name, number of credits for a course and other scheme related information, do visit full semester subjects post given below.
For Computer Science & Engineering 4th Sem scheme and its subjects, do visit CSE 4th Sem 2021 regulation scheme. The detailed syllabus of theory of computation is as follows.
Course Objectives:
Download the iStudy App for all syllabus and other updates.
Unit I
AUTOMATA AND REGULAR EXPRESSIONS 9 Need for automata theory – Introduction to formal proof – Finite Automata (FA) – Deterministic Finite Automata (DFA) – Non-deterministic Finite Automata (NFA) – Equivalence between NFA and DFA -Finite Automata with Epsilon transitions – Equivalence of NFA and DFA- Equivalence of NFAs with and without -moves- Conversion of NFA into DFA – Minimization of DFAs.
Unit II
Download the iStudy App for all syllabus and other updates.
Unit III
CONTEXT FREE GRAMMAR AND PUSH DOWN AUTOMATA 9 Types of Grammar – Chomskys hierarchy of languages -Context-Free Grammar (CFG) and Languages – Derivations and Parse trees – Ambiguity in grammars and languages – Push Down Automata (PDA): Definition – Moves – Instantaneous descriptions -Languages of pushdown automata – Equivalence of pushdown automata and CFG-CFG to PDA-PDA to CFG – Deterministic Pushdown Automata.
Unit IV
Download the iStudy App for all syllabus and other updates.
Unit V
UNDECIDABILITY 9 Unsolvable Problems and Computable Functions -PCP-MPCP- Recursive and recursively enumerable languages – Properties – Universal Turing machine -Tractable and Intractable problems – P and NP completeness – Kruskals algorithm – Travelling Salesman Problem- 3-CNF SAT problems.
Course Outcomes:
Download the iStudy App for all syllabus and other updates.
Text Books:
- Hopcroft J.E., Motwani R. & Ullman J.D., “Introduction to Automata Theory, Languages and Computations”, 3rd Edition, Pearson Education, 2008.
- John C Martin , “Introduction to Languages and the Theory of Computation”, 4th Edition, Tata McGraw Hill, 2011.
Reference Books:
- Harry R Lewis and Christos H Papadimitriou , “Elements of the Theory of Computation”, 2nd Edition, Prentice Hall of India, 2015.
- Peter Linz, “An Introduction to Formal Language and Automata”, 6th Edition, Jones & Bartlett, 2016.
- K.L.P.Mishra and N.Chandrasekaran, Theory of Computer Science: Automata Languages and Computation, 3rd Edition, Prentice Hall of India, 2006.
For detailed syllabus of all other subjects of Computer Science & Engineering, 2021 regulation curriculum do visit CSE 4th Sem subject syllabuses for 2021 regulation.
For all Computer Science & Engineering results, visit Anna University CSE all semester results direct link.