## Syllabus

http://www.gatecse.in/gate-cse-2016-syllabus/#Theory_of_Computation

- Regular expressions and finite automata.
- Context-free grammars and push-down automata.
- Regular and context-free languages, pumping lemma.
- Turing machines and undecidability.

” No changes ”

## 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

### Recommended Tests

- https://gateoverflow.in/exam/242/go-2021-theory-of-computation-1
- https://gateoverflow.in/exam/48/test-by-bikram-theory-of-computation-1
- https://gateoverflow.in/exam/84/test-by-bikram-theory-of-computation-2

### GATE CSE Discussions

77,647 total views, 25 views today