Proving Correctness of DFAs via State Invariants II [FULL EXAMPLE 2] (Theory of Computing)

Channel:

PageWizard Games, Learning & Entertainment

Subscribers:

780

Published on February 3, 2023 3:00:22 PM ● Video Link: https://www.youtube.com/watch?v=Sp0i5b9YIgc

Duration: 36:42

14 views

2

Ms. Kitty joins the fun some more as we revisit our DFA that accepts binary strings with at least three 1s. We show through exploring state invariants how to generalize our DFA further! We then come up with a rather simple/elegant correctness proof by formalizing the state invariants more carefully!

Time Stamps:
0:00 Recap
0:17 Our example, recap of the DFA that recognizes binary strings with at least three 1s.
1:55 State invariants for our DFA, generalizing those concepts to a generalized DFA to accept binary strings with at least f ones.
17:45 Proof of correctness of DFA.
36:22 Closing

Have a beautiful day!

Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
Patreon Supporters (Supporter Access!):
Eric R
-----------------------------------------------------------
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
#automata
#theoryofcomputing