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 Eben 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=9Q4R1ROXrg0

Here we prove (and state) the pumping lemma for context-free languages (CFL), by observing a parse tree of a CFG in Chomsky Normal Form (CNF). The properties of the parse tree allow us to show that if the string generated is big enough, the longest root-to-leaf path in the parse tree must repeat a variable. We utilize this fact to generate more parse trees (i.e., more strings the CFG makes), and look at the properties of parts of this string. 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=-UH9L2sJpPQ

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

(Easy Theory is in 60 FPS now!) Here we look at the problem of showing that regular languages are closed under subsequences (i.e., a substring but doesn't have to be contiguous). The idea is to "eliminate" transitions in the initial DFA by introducing epsilon transitions for every existing transition. We also give a concrete example of this. #easytheory #nfa #dfa #gate #gateconcept #theoryofcomputing #turingmachine #nfatoregex #cfg #pda #undecidable #ricestheorem Contribute: Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs Live Streaming (Sundays 2PM GMT, 2 hours): Twitch: https://www.twitch.tv/easytheory (Youtube also) Mixer: https://mixer.com/easytheory 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 Ultimate Supporters: (none) Diamond Supporters: (none) Platinum Supporters: (none) Gold Supporters: Anonymous (x1), Micah Wood, Ben Pritchard Silver Supporters: Timmy Gy Supporters: Yash Singhal ▶ADDITIONAL QUESTIONS◀ 1. What about "supersequences"? (i.e., all strings that include some string w in L as a subsequence) 2. What about substrings? ▶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 sim ... https://www.youtube.com/watch?v=2bPMta_92tI