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
- [Guide to the Myhill-Nerode Theorem][guide_to_myhill_nerode]
File Attachments
Lecture Recording
The complete archive of this quarter's lecture recordings is available on Canvas.