Cook-Levin Theorem: Full Proof (SAT is NP-complete) Easy Theory 2021-03-16 | Here we give the full proof that SAT is NP-complete, which is a general polynomial-time reduction from any problem B in NP. We use the "tableau" proof which encodes the transitions of a nondeterministic poly-time TM.If you like this content, please consider subscribing to my channel: 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.
Why This All Matters Easy Theory 2024-05-25 | Easy Theory Website: easytheory.orgIf you like this content, please consider subscribing to my channel: 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.
Planar Machines in Theory Easy Theory 2024-05-21 | Here we consider "planar" machines in the undergraduate Theory of Computing class, and whether they are possible to be made, that is, a machine whose drawing does not have edge crossings. We prove that for regular languages, context-free languages, and Turing Machine languages, there is a corresponding "planar" machine. For example, every regular language has a planar NFA. CFG to PDA conversion: youtube.com/watch?v=GwS__G2M8mUTimeline:0:00 - Intro1:38 - Planar NFAs10:00 - Planar PDAs13:24 - Planar Turing MachinesEasy Theory Website: easytheory.orgIf you like this content, please consider subscribing to my channel: 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.
Fourteen DFA Examples? No Problem! Easy Theory 2023-11-30 | Here we solve Sipser problem 1.6, which involves 14 DFA (Deterministic Finite Automaton) problems. I give my strategies as well as ways for solving other problems. Timestamps:0:00 - Intro0:19 - DFA for binary strings beginning with 1, end with 03:02 - DFA for binary strings with at least three 1s4:50 - DFA for binary strings that contain 01018:39 - DFA for binary strings with third symbol 011:01 - DFA for binary strings that start with 0 and odd length, or start with 1 and even length14:59 - DFA for binary strings that do not contain 11018:57 - DFA for binary strings of length at most 520:51 - DFA for binary strings that are not 11 or 11123:42 - DFA for binary strings with every odd position 126:28 - DFA for binary strings with at least two 0s, and at most one 131:29 - DFA for binary strings that are either empty or 033:00 - DFA for binary strings with even 0s or exactly two 1s37:07 - DFAs for emptyset, and all nonempty stringsAll of the transition videos are from StefWithAnF: pexels.com/@stefwithanf-1955763/.If you like this content, please consider subscribing to my channel: 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.
An Update Easy Theory 2023-11-21 | Thanks for supporting the channel and letting us hit 20k subscribers and over 2 million total views!If you like this content, please consider subscribing to my channel: 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.
How to Become a Professor #shorts Easy Theory 2023-05-07 | Easy Theory Website: easytheory.orgIf you like this content, please consider subscribing to my channel: 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.
This CompSci Video was 100% written by ChatGPT Easy Theory 2023-04-01 | ChatGPT can make this video instantly popular, right?...right?Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
[April Fools] Exponential Lower Bounds for Circuit Families (P ≠ NP) Easy Theory 2023-04-01 | Here we prove that P ≠ NP by giving an exponential lower bound for circuit families.If you like this content, please consider subscribing to my channel: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1▶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.The views expressed in this video are not reflective of any of my current or former employers.
Turning 30 Easy Theory 2023-01-25 | Here I give my thoughts about turning 30...yeah...and also some experiences in theory along the way.Timeline:0:00 - Intro0:16 - First Theory (Guest) Lecture1:13 - Theory Recitations1:58 - First Theory Talk3:44 - First Conference Talk5:33 - Dissertation Defense6:31 - OutroIf you like this content, please consider subscribing to my channel: 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.
wish me luck Easy Theory 2023-01-19 | If you like this content, please consider subscribing to my channel: 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.
ChatGPT vs. Professors Computer Science Exam Easy Theory 2022-12-19 | Here we feed questions from a theoretical computer science exam I have given into ChatGPT, and analyze the output answers it gives. (Yes, ChatGPT generated this video description.)For those who may not be familiar, ChatGPT is a state-of-the-art natural language processing system that is capable of generating human-like responses to prompts and questions. In this experiment, we will be testing its ability to understand and accurately respond to questions on a theoretical computer science exam. Throughout the video, you will see me present a series of questions to ChatGPT and observe its responses. I will also be providing my own analysis and thoughts on the accuracy and effectiveness of its responses. This video is intended for those who are interested in the capabilities of natural language processing systems, as well as those studying theoretical computer science who may be curious about the potential use of such systems in their own exams.Timeline:0:00 - Intro0:48 - Question 1 (True/False)15:03 - Question 218:24 - Question 320:58 - Question 422:46 - Question 523:11 - Question 625:33 - Thoughts on ChatGPTIf you like this content, please consider subscribing to my channel: 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.
I proved a math conjecture Easy Theory 2022-11-08 | Original covering arrays video: youtube.com/watch?v=m1j4OBs1wsY&ab_channel=EasyTheoryarXiv preprint: arxiv.org/pdf/2211.01209.pdfHere we discuss a recent proof of mine of a conjecture in my research area, which has to do with sizes of covering arrays. I first go over what the problem, which is determining the asymptotic sizes (# of rows) of covering arrays of "higher index", which is to say each interaction must appear at least a certain number of times, instead of just once. I give "easy" upper and lower bounds; unlike the prior video's scenario, there is a "gap" between them. Next I give some upper bounds that have been published and are "better", but there is still a small gap. My proof this year is that there is no gap between the "easy" lower bound and the new upper bound I prove, which is logarithmic in the number of columns, and additively linear in the index.This proof also uses the probabilistic method, but with a new ingredient: the Lambert W function. My proof first uses the Cauchy-Schwarz inequality on the equation coming from the probabilistic method. The C-S inequality relates cross correlations of sums (hard to understand) to self-correlations (easy to understand), but paying a penalty; in other words, sum(a_i * b_i) changes to sum(a_i^2) * sum(b_i^2) * penalty. Then we use simple known upper bounds on the two sums that come out. The final "trick" is to use the Lambert W function, which is the inverse of f(W) = W * e^W. One would have to analyze the equation that comes out, and notice where in the Lambert W function one is; in this case, it is in the negative region. To finish everything off, we use *lower* bounds on W since in this region, W is negative (which translates to *upper* bounds on covering array sizes).Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
How to Become a Professor in 6 Steps Easy Theory 2022-10-05 | Here we go over the REALLY EASY process of how to become a professor.Timeline:0:00 - Intro0:35 - Step 1: Get a PhD1:17 - Step 2: Starting an Application1:37 - Step 2a: Teaching Statement2:13 - Step 2b: Research Statement2:59 - Step 2c: Letters of Recommendation3:30 - Step 2d: What Website to Apply On4:02 - Step 2e: Advice5:19 - Step 3: Phone Interview6:11 - Step 4: On-Campus Interview8:40 - Step 5: The Waiting Game8:53 - Step 6: CongratulationsEasy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
All Acronyms for Theory of CS class #shorts Easy Theory 2022-10-04 | Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
a student tried to bribe me once Easy Theory 2022-09-29 | Yeah, so that happened. *sigh*Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
The REAL Reason why Math/Humanities arent Useless Easy Theory 2022-09-25 | Here we talk about why ALL classes in university are important, including math AND humanities. The reason is really simple: that we instructors want all of you to be critical thinkers in tackling any complex problem or situation in which you will ever find yourself.Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
I got a scorpion bite before my Ph.D. Defense 🦂 Easy Theory 2022-09-22 | Yeah that really happened.Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1▶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.
The Top Reason Why Im a Professor Easy Theory 2022-09-07 | Here I give the top reason why I'm a professor, involving teaching and helping students. Stock footage provided by Videvo (https://www.videvo.net).Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Rices Theorem Example: Emptiness for Turing Machines Easy Theory 2022-08-17 | 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: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Rices Theorem (Undecidability): 5 Proofs and Examples Easy Theory 2022-08-05 | Here we show 5 different examples of applying Rice's theorem to languages show that each of these languages are undecidable. If you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: Non-Palindromes Easy Theory 2022-08-03 | Here we create a context-free grammar (CFG) for the set of strings that do NOT represent palindromes over {0, 1}. The trick with this language is that we know when a string is not a palindrome, namely when the same position from "either end" of the string is different, for some position. For example, 0100 is not a palindrome because two characters from either end give 1 in one case, and 0 in the other. To finish a CFG, we make characters from either end that are the same until we must (at some point) encounter a "bad" pair. After that (in the "middle") there can be literally any character. Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: Nested Pairs Easy Theory 2022-08-03 | Here we create a context-free grammar (CFG) for the set of all strings of the form 0^n 1^m 2^m 3^n, where n, m are at least 0. This is often called "nested pairs" because the n's are on the outside, and the m's are on the inside. We can effectively just make a CFG for the canonical context-free language 0^n 1^n, and modify it to first handle the 0's and 3's, and then once those are done, transfer control to another variable to handle the 1's and 2's, since m and n are unrelated to each other.Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: Equal Pairs Easy Theory 2022-08-03 | Here we make a context-free grammar (CFG) for the language of all strings of the form 0^n 1^n 2^m 3^m, where n, m are at least 0. Note that we have essentially the same problem twice, and both problems are adjacent to each other. Since m and n are independent of each other, we can just make a small CFG for each, and then put them together with concatenation.Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: Complement of 0^n1^n2^n Easy Theory 2022-08-03 | 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.If you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: {a^i b^j c^k : i at most j+k} Easy Theory 2022-08-03 | Here we create a context-free grammar (CFG) for the language {a^i b^j c^k : i is at most j+k}. This is not inherently a hard language, since we take advantage of the fact that i (the number of a's at the front) is at most j+k (the sum of numbers of b's and c's). Therefore, we can match at most one "a" with every "b", and same with the "c"s. We have to use a different variable (at least in this CFG) to process the b's since there is an order on where the b's appear in the string (they're in the middle).Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammars (CFGs): 5 Intermediate Examples Easy Theory 2022-08-01 | Here we do 5 more intermediate examples of context-free grammars. In general, I give some techniques to analyze the structure of the given language further, such as decomposing the language into a concatenation, or nesting pairs. I also give examples of where we have to analyze the structure of what the strings look like in the language, and break up the CFG into cases which can be handled separately. Timeline:0:00 - Intro0:15 - Example 1: Nested Pairs2:45 - Example 2: Concatenated Pairs4:58 - Example 3: Non-palindromes over {0, 1}8:29 - Example 4: Complement of {0^n 1^n 2^n : n at least 0}15:26 - Example 5: {a^i b^j c^k : i is at most j + k}If you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: (0 U 1)* Easy Theory 2022-07-30 | Here we show how to create a CFG for the language (0 U 1)*.Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: Union/Concat/Star Easy Theory 2022-07-30 | Here we show how to create a context-free grammar for the union and concatenation of any two context-free languages, as well as the star of one such language. The great part of these operations is that the grammars for them can be generated really easily, just by considering the start variables of the original two grammars (and potentially renaming variables).Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: Palindromes Easy Theory 2022-07-30 | Here we create a context-free grammar for the set of palindromes over the alphabet {0, 1}. The purpose of this grammar is to highlight how to deal with the inductive case, as well as why base cases are important.Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: {a^i b^j c^k : i != j} Easy Theory 2022-07-30 | Here we create a context-free grammar for the language {a^i b^j c^k : i != j}. The purpose of this example is to show how dealing with a "not equal" condition on the numbers of characters can be broken down to (1) the first is strictly less than the second, and (2) the second is strictly less than the first. Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammar (CFG) Example: 0*1* Easy Theory 2022-07-30 | Here we create a context-free grammar for the language 0*1*; the purpose of this example is to show why more than one variable is sometimes needed. I realized after I recorded this video that in this case, we could modify the second rule to be S goes to S1, which will guarantee to make the 1s at the end, and does not interfere with the first rule. So another CFG for this would be S goes to 0S | S1 | epsilon. (What I made in the video is called a *regular grammar*, but since we only need to make a context-free grammar, we are not limited by any restriction of where terminals/variables/etc. are.)Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context-Free Grammars (CFGs): 5 Easy Examples Easy Theory 2022-07-29 | Here we go over five examples of making a context-free grammar for a given set of languages. Generally we recommend to look at the properties of the language to build the CFG: how it is built up (via unions, concatenations, etc.), how counts of variables are used, edge cases, etc. The purpose of these five examples are to give an easy baseline of what is generally expected for making CFGs, and I give guidelines for them.Timeline:0:00 - Intro0:15 - Example 1: (0 U 1)*2:16 - Example 2: {0^n 1^m : n, m at least 0}6:07 - Example 3: Palindromes9:09 - Example 4: Union, Concatenation, Star of two CFLs13:19 - Example 5: {a^i b^j c^k : i != j}Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA) Easy Theory 2022-07-22 | Here we show how to convert any context-free grammar (CFG) to an equivalent pushdown automaton (PDA); this video is a more up-to-date and higher-quality version of a video already on the channel.The key idea is to simulate the derivation of some string in the CFG on the stack itself of the PDA. The construction involves building 4 "base" states, and then self loops on the third state for each terminal. Initially push on a $, then the start variable, and pop the $ going to the 4th state. Then, add a series of transitions for every rule, popping the LHS variable, and then pushing on the RHS in reverse order. In this case, we worked with a CFG for the language of strings that are not palindromes (over the alphabet {a, b}), although the particular language/CFG does not matter. Chapters:0:00 - Intro0:26 - Showing CFG is correct1:32 - Overview of CFG to PDA conversion6:52 - Start of CFG to PDA conversion8:04 - Dealing with start variable8:35 - The q_loop state10:25 - Handling terminals at top of stack12:58 - Handling variables at top of stack20:35 - Verifying correctness of conversion23:54 - Outro----------------------------------------------------------------------------------------------------------------What is a context-free grammar? It is a set of 4 items: a set of "variables," a set of "terminals," a "start variable," and a set of rules. Each rule must involve a single variable on its "left side", and any combination of variables and terminals on its right side. See youtube.com/watch?v=h1OSmLSacNA&ab_channel=EasyTheory for more details.What is a pushdown automaton? It is a finite state machine, where on each transition, items can be pushed or popped off of a stack it has, which has unlimited height. See youtube.com/watch?v=Br44Zxv84-Q&ab_channel=EasyTheory for more details.----------------------------------------------------------------------------------------------------------------Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Horses and Colors (Induction False Proof) Easy Theory 2022-07-14 | Here we look at one of the most important problems with regards to proving statements via induction: Sipser's problem 0.12, which asks to show why a proposed proof of a statement about "all horses have the same color" is incorrect. It really gets at the heart of why proofs are important, and why needing to justify every step in a proof is also important.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 EbenEasy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Busy Beaver #4 Turing Machine Simulation Easy Theory 2022-06-05 | This is a simple demonstration of using Manim to simulate a Turing machine tape, in this case the TM being the Busy Beaver winner with 4 states. Interestingly enough: the TM model used for this definition of Busy Beaver was a 2-way infinite tape instead of 1-way that some definitions have, so some special handling was needed to get this to work.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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
How Covering Arrays can Potentially Save Billions in Testing Easy Theory 2022-05-25 | Here we make a short introduction into my research, which is about the intersection of math and computer science, specifically in software testing and making it as efficient as possible. Covering arrays are one model of testing that is very well studied, and this video shows a way of proving the existence of covering arrays with a very low cost compared to exhaustive testing, via a technique called the "probabilistic method."Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Thanks a million. Easy Theory 2022-05-15 | Thanks for a million - onto the next one. Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
Turing Machine Example: a^n b^n c^n Easy Theory 2022-04-20 | Here we give an example of creating a Turing Machine from scratch for the language of all strings a^n b^n c^n where n is at least 0. The trick here is to be able to think at all stages what the TM needs to do, and how the contents on the tape change over time. Also, one only needs to think about the "good" outcomes because any "bad" outcomes can immediately go to the reject state of the TM.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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
Lets Solve This Research Problem Together. Easy Theory 2022-04-18 | Here we present a research problem, which is determining the 5th Busy Beaver number. This problem asks how long a Turing Machine with 5 states can run before it eventually stops, and only a few machines remain. Let's solve it together! Here is the github repo of the current best-known results: github.com/danbriggs/TuringThanks 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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
Sunday Grading with Ryan Easy Theory 2022-04-18 | 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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
The Most Amazing Exam Cheating Story Easy Theory 2022-04-16 | Here we look back at one of the most amazing cheating stories in academia that I have ever witnessed (this time as a graduate student).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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
A nice problem and proof about languages Easy Theory 2022-04-14 | Here we prove the following problem about languages: if L1, L2, and L3 are languages, then (L1 intersect L2) concat L3 = (L1 concat L3) intersect (L2 concat L3).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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
My Responses to Why You Hate Theoretical Computer Science Easy Theory 2022-04-13 | Here we give my reactions to the comments many of you left on my video about seeking your opinions on why you may have "hated" the theoretical computer science class. Yes I read a bunch of Youtube comments for a video. And yes, I now need therapy. The original video is here: youtube.com/shorts/0NYM36nix0YThanks 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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
My Problem with Pushdown Automata and Turing Machines Easy Theory 2022-04-11 | I have beef with PDAs (pushdown automata) and TMs (Turing Machines). Do you think we should fix the problems with them? Discuss below.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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
10 Reasons NO ONE Should Get a Ph.D. Easy Theory 2022-04-09 | Here we give 10 reasons no one (practically) should get a Ph.D.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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
Easy Theory Doesnt Support Academic Integrity Violations...Again Easy Theory 2022-04-07 | Sigh...Don't be stupid. We don't support academic integrity violations here.Easy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: 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.
My Students Disproved a Conjecture Easy Theory 2022-04-07 | Here we talk about an interesting assignment I gave to an intro programming class to disprove a well-known mathematical conjecture, called Euler's Sum-of-Powers Conjecture. I also go through a solution (in Python).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 EbenEasy Theory Website: easytheory.orgBecome a member: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams): streamlabs.com/easytheory1/tipPaypal: paypal.me/easytheoryPatreon: patreon.com/easytheoryDiscord: discord.gg/SD4U3hsMerch:Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel: 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.
Real Professors College Grades 👀 Easy Theory 2022-04-05 | Here we show off my real college grades. Did I get an F in a course? Watch to find out!Thanks to the following supporters of the channel for helping support this video.Dolev Abuhazira, Josh Hibschman, Micah Wood, Morgan Jones, Patrik Keinonen, Simone Glinz, Tao Su, Timothy Gorden, unit220, Valentine EbenEasy Theory Website: easytheory.orgDiscord: discord.gg/SD4U3hsIf you like this content, please consider subscribing to my channel: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1▶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.The views expressed in this video are not reflective of any of my current or former employers.
