Converting DFAs/NFAs to Regular Expressions - Kleene's Construction (Kleene's Theorem (Part 2))
3Here we finish our proof of Kleene's Theorem! To do this, we show that given any DFA, we can convert it in finite time to a regular expression. To do this, we use induction and the concept of a k-path. We describe the conversion process in terms of rounds that are defined inductively. Next time, we'll see an example. Note that the argument applied works regardless if it is a DFA or a NFA.
Note: There may be some artifacts in the video that happened during the live lecture, my apologies for these small graphical defects
Time Stamps:
0:00 Recap of where we were in proving Kleene's Theorem
4:40 Definition of k-path, label of a path
8:10 Examples of k-paths and their relationship with regular expressions of a DFA
19:21 Idea (Gameplan) for proof
24:42 Claim and proof (that presents Kleene's construction/algorithm)
1:02:14 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
#Algorithms
#DataStructures