Lazy Subset Construction (for NFAs to DFAs) [Theory of Computing]

Channel:

PageWizard Games, Learning & Entertainment

Subscribers:

780

Published on March 3, 2023 3:00:01 PM ● Video Link: https://www.youtube.com/watch?v=1hIEc5udL10

Duration: 16:53

19 views

2

In today's lesson we learn about how we can resolve the issue of including unreachable states in a resulting DFA from the subset construction. To do this, we combine the subset construction with a graph-traversal algorithm (in this case breadth-first search).

Time Stamps:
0:00 Recap, issue with the subset construction (please note it is still possible for the DFA to have an exponential number of states, should they be reachable from the start state)
0:44 Lazy Subset Construction
10:08 Example applying the lazy subset construction on a NFA
16:34 Closing

Have a beautiful day!

Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
Eric R.
Patreon Supporters (Supporter Access!):
-----------------------------------------------------------
Become a supporter today! To support my work and mission to provide free or accessible Computer Science education (especially in theory), subscribe to the channel, share my videos. Please donate and contribute to support my work for more content:
PATREON: https://www.patreon.com/PageWizard
SUBSCRIBESTAR: https://www.subscribestar.com/drpage
PAYPAL: https://paypal.me/pagewizard

Follow also at:
FACEBOOK: https://www.facebook.com/DanielRPage
TWITTER: https://twitter.com/PageWizardGLE
QUORA: https://www.quora.com/profile/Daniel-R-Page
TWITCH: https://www.twitch.tv/pagewizard

#ComputerScience
#theoryofcomputing
#automata