Equivalence of Deterministic and Nondeterministic Finite Automata

Channel:
Canada PageWizard Games, Learning & Entertainment
Subscribers:
780
Published on ● Video Link: https://www.youtube.com/watch?v=sAH3ZP_8DB4


Duration: 3:12:28
22 views
2

In today's lecture, we study how DFAs and NFAs recognize the same languages, the regular languages. To do this we study how to construct DFA from NFA, and so on, via the subset (powerset) construction. We see some examples and a proof showing this construction is correct, and ultimately prove the claim that for any NFA there is a DFA that recognizes the same language, and vice-versa.

Time Stamps:
0:00 Preshow
38:05 Lecture Starts

Fill out our form to learn more when we can help you learn computer science together live: https://forms.gle/ergL8FrbHuAHctF3A

Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
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

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

#computerscience
#automata
#theoryofcomputing



Other Videos By PageWizard Games, Learning & Entertainment


2023-02-22Regular Expressions I
2023-02-20What are Nondeterministic Finite Automata? [Theory of Computing]
2023-02-17Dan Plays Chrono Trigger (February 16, 2023)
2023-02-17Rows of Pascal's Triangle Sum to Powers of 2 (Mathematics for Computer Science)
2023-02-15Applying the Binomial Theorem (Mathematics for Computer Science)
2023-02-15Nondeterministic Finite Automata with Epsilon-Transitions
2023-02-13The Binomial Theorem (Mathematics for Computer Science)
2023-02-10Dan Plays Monster Hunter Rise: Sunbreak (February 9, 2023)
2023-02-10Properties of Pascal's Triangle (Mathematics for Computer Science)
2023-02-08Pascal's Triangle and Formula (Mathematics for Computer Science)
2023-02-08Equivalence of Deterministic and Nondeterministic Finite Automata
2023-02-06n Choose k Equals n Choose n-k
2023-02-03Dan Plays Pokemon Scarlet (FINALE - Feb. 2, 2023)
2023-02-03Proving Correctness of DFAs via State Invariants II [FULL EXAMPLE 2] (Theory of Computing)
2023-02-01Ms. Kitty Disrupts Dr. Page's Lecture All Wet
2023-02-01Proving Correctness of DFAs via State Invariants [FULL EXAMPLE] (Theory of Computing)
2023-02-01Nondeterminism and Nondeterministic Finite Automata
2023-01-30Proving Correctness of Deterministic Finite Automata, State Invariants (Theory of Computing)
2023-01-27Formal Definition of Computing for DFAs (Theory of Computing)
2023-01-25Regular Operators (Theory of Computing)
2023-01-23Designing Deterministic Finite Automata (DFAs) [Theory of Computing]


Tags:
automata theory
computer science
automata
NFA
DFA