Theory of computation.
:: 335 Words

Here are some good slides by Prof. S. Akshay and Prof. Ashutosh Gupta at IIT Bombay

Textbooks:

  • Introduction to the theory of computation -- very concise theory, with more focus on ideas than rigor, tricky exercises. We followed this for our CS2200 course at IIT Madras
  • Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani, and Ullman - Very detailed, less exercises but rigorous proofs.
  • Automata and Computability, Dexter C. Kozen

Possible workflow

  • TOC is a very proof oriented course and requires a good understanding of discrete math and proof writing. TOC -- especially CFGs help you build foundations for Programming Languages and Compilers. One possible structure is (Please Note that this is only a suggestion -- everyone has their own way of learning things):
  • Follow the NPTEL playlist
  • Solve the problem sets here -- click on the lectures link
  • If you get time try solving some questions from Sipser although above problems should be good enough to give you strong foundations. If you are not sure about which ones, have a look
  • Writing and iterating over a proof is necessary to see urself grow on this skill -- yes proof writing is a very valuable skill :) and comes only by doing
  • Solve exams

I do not have solutions to these problems, but a lot of solutions to Sipser's textbook are available online, although it is worth giving the problems some thought before jumping over to the solutions.