▶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=8BXxptA3WPE
Here we give a proof of Ogden's Lemma, which is a generalization of the pumping lemma for context-free languages. It's the same general idea, except now we can arbitrarily mark a number of symbols in the string, and the decomposition of the string contains some number of marked symbols. This generalizes the usual pumping lemma because the usual PL has "marked" symbols as being all of the symbols in the string. But for Ogden's Lemma, we can have some unmarked characters.
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, 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=_95IZWDRHNQ
Here we prove that the emptiness problem for Turing Machines is undecidable via Rice's theorem; this problem is also known as the E_TM problem. This is a simple application of Rice, and all we need to do is to show that the language is a nontrivial property of TM languages. The example TMs needed are very easy and straightforward.
Easy Theory Website: https://www.easytheory.org
Discord: https://discord.gg/SD4U3hs
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
...
https://www.youtube.com/watch?v=b33N0rDhVlY
Here we show that A_REX is decidable, which is the problem of determining if a given regular expression can generate a given string. We show that this is decidable by converting the regex into an equivalent NFA, and calling the decider for A_NFA on that NFA and the same input string. Since the NFA and regex are equivalent, the answer reported is the same. Since all steps take finite time, this shows A_REX is decidable.
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=sPzvKqp0MBc
Here we introduce the notion of "logarithmic space", which is understanding what problems can be solved with a "very small" amount of space. We define what a Turing Machine needs to do in order to achieve that, as well as give some example problems that are in deterministic log space, and nondeterministic log space.
What is space in complexity theory? It is the maximum amount of cells used on a Turing Machine that runs on inputs of size n. See https://www.youtube.com/watch?v=yMhQdU5j6ag&t=8s&ab_channel=EasyTheory for more details.
Timeline:
0:00 - Intro
2:30 - Model for Small Space
7:30 - Definition of Log Space and Nondet Log Space
8:30 - All regular languages are in L
15:05 - {0^n 1^n} is in L
18:25 - PATH vs DPATH, DPATH in NL
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=X9R6mvENyQQ
This is another jest at all complexity theory computer science professors (me included). Here we show some more memes of the complexity theory computer science class. If you want to actually learn some of the real stuff behind the memes, there are lots of playlists in my channel (including the one linked to in the card). The truth is that Computer Science (and this class, especially) is a hard major, and sometimes there is a disconnect between students and professors. This is one of the motivations behind why I'm doing what I'm doing with this channel.
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, 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=m30xitLID-4
Here we show that the E_TM problem is undecidable. We suppose that it were decidable, then construct a decider for the A_TM problem, which cannot possibly exist. The key idea is to make a new machine that has empty language iff M accepts w.
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.
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
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=iN0auyB0Hv0
Here we create a context-free grammar (CFG) for the complement of the language of all strings of the form 0^n 1^n 2^n. The original (non-complemented) language is famously not context-free, so there has to be special properties of the complemented version that we have to take advantage of. I just give a brief sketch of the grammar in this video, because the grammar is somewhat large, repetitive, and most of what isn't shown is either (1) an almost copy of something else I show, or (2) is regular, which is not that interesting since it is already context-free.
Easy Theory Website: https://www.easytheory.org
Discord: https://discord.gg/SD4U3hs
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
...
https://www.youtube.com/watch?v=gGg_4rap-VA
Here we review a code submission from codereview.stackexchange.com on finding Pythagorean triples in Python. This is the same as Problem 9 from Project Euler.
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below.
Dolev Abuhazira, Josh Hibschman, Micah Wood, Morgan Jones, Patrik Keinonen, Simone Glinz, Tao Su, Timothy Gorden, unit220, Valentine Eben
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=4fHCso_c03U
Here we go over a GATE exam problem about a language of Turing Machines that accept some string of length 2020. We then classify this language as being undecidable but recognizable. The proof of undecidability is supposing a decider for it exists, then obtaining a decider for A_TM from that, which we know cannot exist. The proof of recognizable comes from "brute force" parallel simulation of all strings of length 2020, and accepting if any such string is accepted.
Patreon: https://www.patreon.com/easytheory
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ADDITIONAL QUESTIONS◀
1. Could we have applied Rice's Theorem to this problem?
2. What can we say about the complement of L?
▶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.
...
https://www.youtube.com/watch?v=YSgmw9t7OQs