Published By
Created On
8 Oct 2021 17:13:09 UTC
Transaction ID
Cost
Safe for Work
Free
Yes
Office Hours #7 with Easy Theory - NFA to DFA, GNFA Conversion (NFA to Regular Expression)
Powered by Restream https://restream.io/
Patreon: https://www.patreon.com/easytheory
Twitch: https://www.twitch.tv/easytheory
Mixer: https://mixer.com/easytheory
Discord: https://discord.gg/SD4U3hs
Facebook: https://www.facebook.com/easytheory/
Twitter: https://twitter.com/EasyTheory
Teespring: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions.
This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them are tractable, i.e. we can build efficient algorithms to reason with objects such as finite automata, context-free grammars and pushdown automata. For example, we can model a piece of hardware (a circuit) as a finite-state system and solve whether the circuit satisfies a property (like whether it performs addition of 16-bit registers correctly). We can model the syntax of a programming language using a grammar, and build algorithms that check if a string parses according to this grammar.
On the other hand, most problems that ask properties about Turing machines are undecidable. This Youtube channel will help you see and prove that several tasks involving Turing machines are unsolvable---i.e., no computer, no software, can solve it. For example, you will see that there is no software that can check whether a C program will halt on a particular input. To prove something is possible is, of cours
...
https://www.youtube.com/watch?v=NnYhVt-dB8U
Patreon: https://www.patreon.com/easytheory
Twitch: https://www.twitch.tv/easytheory
Mixer: https://mixer.com/easytheory
Discord: https://discord.gg/SD4U3hs
Facebook: https://www.facebook.com/easytheory/
Twitter: https://twitter.com/EasyTheory
Teespring: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions.
This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them are tractable, i.e. we can build efficient algorithms to reason with objects such as finite automata, context-free grammars and pushdown automata. For example, we can model a piece of hardware (a circuit) as a finite-state system and solve whether the circuit satisfies a property (like whether it performs addition of 16-bit registers correctly). We can model the syntax of a programming language using a grammar, and build algorithms that check if a string parses according to this grammar.
On the other hand, most problems that ask properties about Turing machines are undecidable. This Youtube channel will help you see and prove that several tasks involving Turing machines are unsolvable---i.e., no computer, no software, can solve it. For example, you will see that there is no software that can check whether a C program will halt on a particular input. To prove something is possible is, of cours
...
https://www.youtube.com/watch?v=NnYhVt-dB8U
Author
Content Type
Unspecified
video/mp4
Language
English
More from the publisher
Controlling
VIDEO
PROOF
proof-by-contradiction-(+-examples!)
Here we introduce the idea of proof by contradiction, which is a technique of proving that the opposite of a claim cannot possibly be true (by deriving a contradiction). We show that sqrt(2) cannot be rational, and that there are no integers p, q such that p^2 - 4q = 2.
Easy Theory Website: https://www.easytheory.org
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=i9KTtaKjGac
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English
Controlling
VIDEO
NONDE
nondeterminism-incurs-exponential-blowup
Here we show that one can make a deterministic TM from a nondeterministic one that takes at most exponentially longer.
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=cmODkcCgen4
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English
Controlling
VIDEO
THE R
the-recursion-theorem-proof-+-examples
Here we prove the recursion theorem, which is one of the most important results in computability theory. This informally shows that any Turing Machine can "obtain" its own description on the tape, and then compute something with it. This video follows Sipser's presentation of the recursion theorem, with slight alterations to make understanding easier. The recursion theorem is not super difficult to show, but it gives the theorist a strong tool to show that many languages are undecidable, not recognizable, or even not computable in only a few lines.
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su
Timeline:
0:00 - Intro
0:15 - Informal Description of Recursion Theorem
1:29 - The convert_to_TM function
3:50 - Construction of the SELF Turing Machine
10:15 - Formal Statement of Recursion Theorem
12:26 - Proof of the Recursion Theorem
17:45 - Example 1: A_TM is not Decidable
20:23 - Example 2: MIN_TM is not Recognizable
What is a Turing Machine? It is a state machine that has a set of states, input, tape alphabet, a start state, exactly one accept state, and exactly one reject state. See https://www.youtube.com/watch?v=j0bIxPqlYLE&ab_channel=EasyTheory for more details.
▶CONTRIBUTE◀
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=iXpp5X6WPkE
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English
Controlling
VIDEO
PUMPI
pumping-lemma-+-examples-intro-theory-of
Here we go over the pumping lemma for regular languages as well as prove some languages are not regular, including proof strategies. This was recorded on 13 February 2017.
Timeline:
0:00 - Intro
4:00 - Pumping Lemma Statement
14:00 - Pumping Lemma Example 1 (0^n 1^n 2^n)
25:00 - Pumping Lemma Example 2 (0^3n 1^2n 2^n)
29:00 - Pumping Lemma Example 3 (Perfect Squares)
40:00 - Pumping Lemma Example 4 (Primes)
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=caNOYi1gkXA
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English
Controlling
VIDEO
THE "
the-simple-post-correspondence-problem
Here we show that Simple PCP is decidable (over an alphabet over size 1), and give open problems about the number of tiles for PCP and decidability. NOTE: the open problems at the end are about the number of tiles, NOT the alphabet size! It is undecidable for alphabets of size 2 or more.
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=H4Uk1Qvsuwo
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English
Controlling
VIDEO
GOOD
good-luck-in-spring-2022!-shorts
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Dolev Abuhazira, Simone Glinz, Timmy Gy, Josh Hibschman, Morgan Jones, Patrik Keinonen, Travis Schnider, and Tao Su
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=lC9751Q-G0U
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English
Controlling
VIDEO
QUOTI
quotient-languages-(cool-regular
Here we look at "quotient languages" and show an advanced topic in theory of computation - that we can show a DFA exists without knowing how to produce it. Moreover, we show that regular languages are closed under quotient, but also closed under quotient with any language at all!
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory #gate #theory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=PgUB_07N0eA
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English
Controlling
VIDEO
LINEA
linear-time-median-algorithm-(making
Here we show that we can find the median of an array (or in general, the kth smallest element) in linear time, versus just sorting the array and returning the kth element. This in turn speeds up Quicksort, because the pivot can now be the median element (findable in linear time), and we now get the guaranteed performance of Mergesort, which was O(n log n). Before, Quicksort can at worst pick the "first" element every time, which caused a O(n^2) runtime to occur.
Timestamps:
0:00 - Intro
0:31 - Problem Statement
3:28 - Can we find a good pivot?
6:37 - Generalize the problem (finding kth smallest/largest)
7:45 - Kth Smallest/Largest "Simple" Recursive Algorithm
13:25 - Can we make this algorithm faster?
15:10 - Median of Medians
20:50 - Modifying Kth Smallest/Largest Algorithm
24:55 - Proving this algorithm is faster
29:00 - Determining algorithm runtime
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=n8cyxDtp9t4
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English
Controlling
VIDEO
DOES
does-veritasium's-hilbert's-infinite
Here we address how accurate Veritasium's video about infinite hotels and countable vs uncountable infinities is. The video is here: https://www.youtube.com/watch?v=OxGsU8oIWjY&vl=en&ab_channel=Veritasium
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Timmy Gy, Josh Hibschman, Patrik Keinonen, Travis Schnider, and Tao Su
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=2uxElkiaUPw
Transaction
Created
2 weeks ago
Content Type
Language
video/mp4
English