Anna University, Subject code – CS3452, deals with the B.E Computer Science and Engineering Semester -IV Theory Of Computation syllabus regulation 2021 relating to affiliated institutions. From here, Students can get assistance in preparing notes to excel in academic performance.
We include every topic of the Theory Of Computation Syllabus, to understand the subject very well. It will help you to improve your idea of syllabus of CS3452-Theory Of Computation Syllabus on your finger tips to go ahead in a clear path of preparation. In this following article Theory Of Computation Syllabus, will help you, Hope you share with your friends.
If you want to know more about the syllabus of B.E Computer Science and Engineering connected to an affiliated institution’s under four-year undergraduate degree programme. We provide you with a detailed Year-wise, semester-wise, and Subject-wise syllabus in the following link B.E Computer Science and Engineering Syllabus Anna University, Regulation 2021.
Aim Of Concept:
- To understand foundations of computation including automata theory
- To construct models of regular expressions and languages.
- To design context free grammar and push down automata
- To understand Turing machines and their capability
- To understand Undecidability and NP class problems
CS3452- Theory Of Computation Syllabus
Unit I: Automata And Regular Expressions
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: Regular Expressions And Languages
Regular expression – Regular Languages- Equivalence of Finite Automata and regular expressions – Proving languages to be not regular (Pumping Lemma) – Closure properties of regular languages.
Unit III: Context-Free Grammar And Push-Down Automata
Types of Grammar – Chomsky‘s 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: Normal Forms And Turing Machines
Normal forms for CFG – Simplification of CFG- Chomsky Normal Form (CNF) and Greibach Normal Form (GNF) – Pumping lemma for CFL – Closure properties of Context-Free Languages –Turing Machine: Basic model – definition and representation – Instantaneous Description – Language acceptance by TM – TM as Computer of Integer functions – Programming techniques for Turing machines (subroutines).
Unit V: Undecidability
Unsolvable Problems and Computable Functions –PCP-MPCP- Recursive and recursively enumerable languages – Properties – Universal Turing machine -Tractable and Intractable problems – P and NP-completeness – Kruskal’s algorithm – Travelling Salesman Problem- 3-CNF SAT problems.
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.
References:
- 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.
Related Posts On Semester – IV:
- CS3491 – Artificial Intelligence and Machine Learning
- CS3492 – Database Management Systems
- CS3401 – Algorithms
- CS3451 – Introduction to Operating Systems
- GE3451 – Environmental Sciences and Sustainability