What problems are too hard to be solved by DFAs? What can't you write a regular expression for? And how do we even conceptualize this question? This lecture explores distinguishability, a key technique in approaching this, and the Myhill-Nerode theorem, a powerful tool for proving languages aren't regular.
Readings
Links
Lecture Recording
The complete archive of this quarter's lecture recordings is available on Canvas.