CS3452 Theory of Computation Notes
Download CS3452 Theory of Computation Books, Lecture Notes, Part-A 2 marks with answers, Part-B 16 marks Questions, PDF Books. In this Notes Very Useful for Second Year Fourth Semester Students.
“CS3452 Theory of Computation Books”
“CS3452 Theory of Computation Lecture Notes”
“CS3452 Theory of Computation Study Material”
“CS3452 Theory of Computation Notes”
Subject Info:
| Semester | Fourth Semester |
| Department | CSE |
| Year | Second Year |
| Regulation | R 2021 |
| Subject Code / Name | CS3452 Theory of Computation |
| Content | Local Authors Books, Lecture Notes |
Syllabus:
CS3452 Theory of Computation
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.