Theory of Computation detailed syllabus for Information Technology (IT) for 2021 regulation curriculum has been taken from the Anna University official website and presented for the IT 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 Information Technology 4th Sem scheme and its subjects, do visit IT 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 Information Technology, 2021 regulation curriculum do visit IT 4th Sem subject syllabuses for 2021 regulation.
For all Information Technology results, visit Anna University IT all semester results direct link.