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.