Theory of Computing

Finite automata and regular expressions, context-free grammars and push-down automata,
non-determinism. Context-sensitive grammars and the Chomsky hierarchy of grammars.
Turing machine and the halting problem. Undecidable problems. Church’s Conjecture and its
implications.