This course is originally intended for the IT students of CBPGECJ who are taking the course on ETCS-206, affiliated to GGSIPU. This is a B.Tech IT syllabus directly taken from Guru Gobind Singh Indraprastha University. The main objective of this course is to understand fundamental requirements for building algorithms of any language.
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). [ T1,T2][No. of hrs. 11]
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. [T1,T2][No. of hrs. 11]
Turing machines, Turing Church’s Thesis, Variants and equivalence of Turing Machine, Recursive and recursively enumerable languages, Halting problem, Undecidability, Examples of Undecidable problem. [ T1,T2][No. of hrs. 11]
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. [ T1,T2][No. of hrs. 11]
[T1] Hopcraft, Motwani, Rajiv and Ullman, “Introduction to Automata Theory, Languages and Computation", Third Edition, Pearson.
[T2] Sipser, Michael, ”Introduction to the theory of Computation”, Third Edition, Cengage.
[R1] Martin J. C., “Introduction to Languages and Theory of Computations”, Third Edition, TMH.
[R2] Papadimitrou, C. and Lewis, C.L., “Elements of the Theory of Computation”, PHI.
[R3] Daniel I.A. Cohen, ”Introduction to Computer Theory”,Second Edition, John Wiley.