Mastering Subset Construction: Converting NFA-ε to DFA in Automata Theory 🤖

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 video is part of a series on Formal Languages and Automata that forms the last section of the Discrete Mathematics course for first year computer scientists.

In this video I explain how, given any NFA-epsilon, you can build an equivalent DFA, at the cost of an exponential growth in the number of states.

It feels very rewarding to derive the definition of the DFA yourself, as opposed to reading it from the slides. Once you are able to do that, you will be in a good position to understand the theorem in the next video, which proves the equivalence of the two automata.

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