Theory of Computation - A blended Course (ETCS - 206) for the Students of CBPGECJ, New Delhi


Srinivasa K G

Dr. Srinivasa K G

Srinivasa K G received his PhD in Computer Science and Engineering from Bangalore University in 2007. He is the recipient of All India Council for Technical Education – Career Award for Young Teachers, ISTE – ISGITS National Award for Best Research Work Done by Young Teachers, Institution of Engineers(India) – IEI Young Engineer Award in Computer Engineering, Rajarambapu Patil National Award for Promising Engineering Teacher Award from ISTE – 2012, IMS Singapore – Visiting Scientist Fellowship Award. He has published more than hundred research papers and text books in International Conferences and Journals. He has visited many Universities abroad as a visiting researcher – He has visited University of Oklahoma, USA, Iowa State University, USA, Hong Kong University, Korean University, National University of Singapore are few prominent visits. He has been awarded BOYSCAST Fellowship by DST.

Reviews (10)

Utkarsh Pandey
Nyce course with splendid opportunities to gain and best thing was to be awared about online courses.
Manish Kumar
manoj kumar
Ankit kumar


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]

Text Books:

[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.

References Books:

[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. 

Course content

Request invitation

Content of this course is available by invitation only. You can not access this course if you don't have an invitation from the course instructor.

Get Started

Interested? Start your first course right now.

There is more to learn