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
File Attachments
Lecture Recording
The complete archive of this quarter's lecture recordings is available on Canvas.