+- studentsuvidha (https://studentsuvidha.com/forum)
+-- Forum: Student Stuffs (https://studentsuvidha.com/forum/Forum-Student-Stuffs)
+--- Forum: Indraprastha University IPU notes and papers (https://studentsuvidha.com/forum/Forum-Indraprastha-University-IPU-notes-and-papers)
+---- Forum: IPU B.tech/ B.E. papers and Notes -free downloads (https://studentsuvidha.com/forum/Forum-IPU-B-tech-B-E-papers-and-Notes-free-downloads)
+----- Forum: IPU B.tech/ B.E. C.Sc. papers and Notes -free downloads (https://studentsuvidha.com/forum/Forum-IPU-B-tech-B-E-C-Sc-papers-and-Notes-free-downloads)
+------ Forum: 4th semester IPU B.tech CSC papers and Notes -free download (https://studentsuvidha.com/forum/Forum-4th-semester-IPU-B-tech-CSC-papers-and-Notes-free-download)
+------ Thread: Theory of Computation IPU IT notes and question paper free download (/Thread-Theory-of-Computation-IPU-IT-notes-and-question-paper-free-download)
Theory of Computation IPU IT notes and question paper free download - Dipesh S - 05-01-2017
QUESTION PAPERS:- SYLLABUS:-
UNIT- I
Overview: Alphabets, Strings & Languages, Chomsky Classification of Languages, Finite Automata, Deterministic finite Automata (DFA) & Nondeterministic finite Automata (NDFA), Equivalence of NDFA and DFA, Minimization of Finite Automata, Moore and Mealy machine and their equivalence, Regular expression and Kleen’s Theorem(with proof), Closure properties of Regular Languages, Pumping Lemma for regular Languages(with proof).
UNIT- II
Context free grammar, Derivation trees, Ambiguity in grammar and its removal, Simplification of Context Free grammar, Normal forms for CFGs: Chomsky Normal Form & Greibach Normal Form, Pumping Lemma for Context Free languages, Closure properties of CFL(proof required), Push Down Automata (PDA), Deterministic PDA, Non Deterministic PDA ,Equivalence of PDA and CFG, Overview of LEX and YACC.
UNIT- III
Turing machines, Turing Church’s Thesis, Variants and equivalence of Turing Machine, Recursive and recursively enumerable languages, Halting problem, Undecidability, Examples of Undecidable problem.
UNIT- IV
Introduction to Complexity classes, Computability and Intractability, time complexity, P, NP, Co-NP, Proof of Cook’s Theorem, Space Complexity, SPACE, PSPACE, Proof of Savitch’s Theorem, L ,NL ,Co-NL complexity classes.