Computer Science Theory Summer 2021: Lecture 2 (Part 3/3)

This is Lecture 2 (Part 3/3) for COMS W3261: Computer Science Theory, offered Summer B 2021 at Columbia University. In this lecture, we prove that NFAs recognize the set of regular languages. We do this by showing that for any NFA, we can create an equivalent DFA. Course website: https://twrand.github.io/3261-sum21.html Link to video notes: twrand.github.io/pdfs/notability/COMSW3261_Lecture2.3_notability.pdf