NFA-e and DFA: Proving They Recognize the Same Language 🧠

I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This is the first video in a series on Formal Languages and Automata that forms the last part of the Discrete Mathematics course for first year computer scientists.

In this video I prove a beautiful theorem stating that the DFA we produced in the previous video with the subset construction recognizes exactly the same language as the NFA-epsilon from which we derived it.

The proof consists of two halves. First, that every string recognized by the NFA-epsilon is also recognized by the DFA. Second, that every string recognized by the DFA is also recognized by the NFA-epsilon. The conclusion is that the two sets of strings are identical.

Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it.


Course web page:
https://www.cl.cam.ac.uk/teaching/current/DiscMath/


Course handout:
https://www.cl.cam.ac.uk/teaching/2021/DiscMath/2021-stajano-discmath-handout.pdf


My home page:
http://frank.stajano.com