Some notes from theory of computation (6.840, Fall 2013)

Some notes from theory of computation (6.840, Fall 2013), taught by Prof. Michael Sipser.

• Space and time complexity theorems
• DFAs and CFGs
• How to prove decidability
• Oracles
• Pumping lemmas
• Reductions
• Time and space classes