Syllabus
http://www.gatecse.in/gate-cse-2016-syllabus/#Theory_of_Computation
- pumping lemma newly added. So, questions based on pumping length or some examples can be asked.
- Recursively enumerable sets removed but Turing machines are there. So, this should not really matter.
Book
Video
You won’t get better video for TOC than Shai Simonson’s.
Web Links
- Regular Expressions – Stanford slides
- NFA-DFA
- Finite Automata + Pumping lemma – MIT slides
- PDA, CFG
- Turing Machine Handout
- Example Reductions
- MIT Notes
Previous Year Questions
http://gateoverflow.in/questions/automata-theory
Important Questions
http://gateoverflow.in/blog/21/important-questions-in-theory-of-computation
