Automata Theory and Formal Languages

This is the theory backbone of CS: you'll learn what counts as "computation" by climbing a hierarchy of abstract machines — finite automata, pushdown automata, Turing machines — and proving what each can and cannot do. Most of the work is pencil-and-paper: constructing machines and grammars, applying pumping lemmas to show a language is impossible, doing reductions to prove problems undecidable or NP-complete, all anchored in Sipser. It sits on top of your discrete math foundation and pays off everywhere downstream — compilers, algorithms, cryptography — by giving you the vocabulary to say *why* a problem is hard rather than just that your code is slow.