Regular Expressions II (Regex to DFA - Kleene's Theorem (Part 2))

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


Duration: 2:39:37
9 views
1

We now finish up the rest of our journey studying Kleene's Theorem! We also learn some properties of regular languages!

Two important remarks:
1) For some silly reason I was treating the induction part of the construction during lecture as the induction step of a proof, that's the intuition around it indeed but it sort of gets away from the proof itself. The idea here is that we know how to build regex for (k-1)-paths, and show how to get the next "round" of regex! When proving the claim, we care that the construction captures the k-paths from one state to another and notice that we use the prior round to construct the next round (that's where the reasoning for the induction comes from).
2) In addition, the proof translates perfectly for NFAs (we did it for DFAs), it is only epsilon-NFAs where you need to do a bit more work (and at that stage it is kind of silly, as you can convert the epsilon-NFA over to an NFA or DFA).

Both of these will be refined in their corresponding lecture videos, look out for those when they become available toward the end of March 2023.

Time Stamps:
0:00 Preshow
23:03 Lecture begins!

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):
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

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
#regex
#kleene



Other Videos By PageWizard Games, Learning & Entertainment


2023-03-15Introduction to Cryptography
2023-03-13What are Nondeterministic Finite Automata with Epsilon-Transitions? (Theory of Computing)
2023-03-10Equivalence of Nondeterministic and Deterministic Finite Automata (Theory of Computing)
2023-03-10Dan Plays Chrono Trigger (March 9, 2023)
2023-03-08Proving the Correctness of the Subset Construction (Theory of Computing)
2023-03-07Pumping Lemma for Regular Languages (Birthday Stream)
2023-03-06Applying the Lazy Subset Construction for NFAs (to DFAs) [Theory of Computing]
2023-03-03Lazy Subset Construction (for NFAs to DFAs) [Theory of Computing]
2023-03-03Dan Plays Chrono Trigger (March 2, 2023)
2023-03-01Subset Construction: NFAs to DFAs (Theory of Computing)
2023-03-01Regular Expressions II (Regex to DFA - Kleene's Theorem (Part 2))
2023-02-27Proving NFAs are Correct via State Invariants (Theory of Computing)
2023-02-24Designing Nondeterministic Finite Automata (Theory of Computing)
2023-02-24Dan Plays Chrono Trigger (February 23, 2023)
2023-02-22Formal Definition of Computing for NFAs (Theory of Computing)
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


Tags:
rege
regex
regexp
kleene
automata