Undecidable Languages - Easy Theory

Currently Playing: Why There's (Likely) No Pumping Lemma for Context-Sensitive Languages

Credit: https://cs.stackexchange.com/a/60791 Here we give an involved proof to give strong evidence that there is no "pumping lemma for context-sensitive languages." The idea is that if there is one, then one can show that the "infinity" problem for that model is recognizable, but this is impossible for CSLs because that problem is unrecognizable (as we prove with linear bounded automata). Timeline: 0:00 - Intro 1:20 - What does a "pumping lemma" mean? 6:45 - If the predicate exists, then Infinity Problem is recognizable 13:43 - Infinity Problem for LBAs is not recognizable 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 ▶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.