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.
Today's recording will be embedded on this page shortly after lecture.