Categories
Important question Notes question bank Question Paper R-2021 Syllabus

CS3452 Theory of Computation [PDF]

CS3452 Theory of Computation Study Materials

Anna University – CS3452 Theory of Computation Regulation 2021 Syllabus , Notes , Important Questions, Question Paper with Answers Previous Year Question Paper.

UNIT I AUTOMATA AND REGULAR EXPRESSIONS CS3452 Theory of Computation Syllabus

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 CS3452 Theory of Computation Notes

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 CS3452 Theory of Computation Important Questions

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 CS3452 Theory of Computation Question Bank

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 CS3452 Theory of Computation Question Paper

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.

Syllabus Click Here
Notes Click Here
Important Questions Click Here
Previous Year Question Paper Click Here
Question Bank Click Here

TEXT BOOKS: CS3452 Theory of Computation Notes

1. Hopcroft J.E., Motwani R. & Ullman J.D., “Introduction to Automata Theory, Languages and
Computations”, 3rd Edition, Pearson Education, 2008.
2. John C Martin , “Introduction to Languages and the Theory of Computation”, 4th Edition, Tata
McGraw Hill, 2011.

REFERENCES: CS3452 Theory of Computation Important Questions

1. Harry R Lewis and Christos H Papadimitriou , “Elements of the Theory of Computation”, 2nd
Edition, Prentice Hall of India, 2015.
2. Peter Linz, “An Introduction to Formal Language and Automata”, 6th Edition, Jones & Bartlett,
2016.
3. K.L.P.Mishra and N.Chandrasekaran, “Theory of Computer Science: Automata Languages and
Computation”, 3rd Edition, Prentice Hall of India, 2006.

Related Links

Anna University Syllabus Regulation 2021

Anna University Regulation 2021 Study Materials

Anna University Results

CGPA Calculator For Anna University

Download Padeepz App for Android

 

Leave a Reply

Your email address will not be published. Required fields are marked *