What are Nondeterministic Finite Automata? [Theory of Computing]

Channel:

PageWizard Games, Learning & Entertainment

Subscribers:

780

Published on February 20, 2023 2:45:00 PM ● Video Link: https://www.youtube.com/watch?v=3HC68-tnEzM

Duration: 1:02:30

18 views

3

We carefully explore the concept of nondeterminism in theory of computation, in the context of nondeterministic finite automata. We begin with deterministic finite automata and see how we could generalize it to be nondeterministic. We see a couple ways to think about nondeterminism, and how to define such a machine for finite automata!

Time Stamps:
0:00 Walkthrough and reminder of DFAs, how does a DFA process strings? A couple questions
14:05 What if we allow the machine to transition into multiple states? Nondeterminism.
22:35 A couple intuitions. Perfect guessing, and (massively) parallel threads.
40:04 Definition of nondeterministic finite automaton (NFA)
45:17 Example NFA, its transition table and transition diagram.
55:10 Example processing a string on our example NFA
1:02:10 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
#theoryofcomputation
#automata