Proving Correctness of DFAs via State Invariants [FULL EXAMPLE] (Theory of Computing)
4Ms. Kitty joins me in helping prove the correctness of another deterministic finite automaton (DFA). We designed this DFA in a previous lecture, but we use state invariants we derive together to prove its correctness (that it works the way we claim)! Ms. Kitty keeps me honest, so join the fun!
Time Stamps:
0:00 Opening and Recap
1:00 Revisiting our DFA that detects in binary strings the substring 01. What are some state invariants? Tips on discovering state invariants.
12:13 Proof of correctness of our DFA
40: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