Here we prove that the language of all strings with more 1s than 0s is not regular. The trick here is to structure the string "well" (i.e., it's easy to add characters, so we want 0s first instead of 1s) and then apply the pumping lemma in the usual way. 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. 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=3CN6QCQYFpk

Here we look at three languages, and show some are regular and some are not. Recall that a language is regular if some deterministic finite automaton (DFA) recognizes it. The languages are: 1. L_0,1 - set of all strings with equal numbers of 0s and 1s 2. L_01,10 - set of all strings with equal numbers of 01s, and 10s 3. L_0,01 - set of all strings with equal numbers of 0s and 01s We show that some of these are regular by producing either a regular expression for them, or that they are not regular by showing a comparison with an existing non-regular language. Patreon: https://www.patreon.com/easytheory Facebook: https://www.facebook.com/easytheory/ Twitter: https://twitter.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. What if Sigma = {0, 1, 2}? (Hint: the answers are not all the same.) 2. Which y, z are such that L_y,z is regular? What about context-free? 3. For the ones in which L_y,z is regular, how many states are needed in a DFA to recognize them? ▶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 add ... https://www.youtube.com/watch?v=KWCDQVdFmq0

Here we show that regular languages are closed under reversal, and give some tips on why the "usual" proof is not quite right. The main idea is to take a DFA for the language, and reverse all of its transitions. The problem is that the resulting machine may not necessarily be a DFA or even an NFA. But by observing what the resulting language should be (the reverse of all the strings), we can make some adjustments to it to make it work, which we cover in the video. #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. How large will the "reverse" DFA be in relation to the original one? (after converting from an NFA to DFA) 2. What if we ask all strings such that some substring of it is reversed? ▶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 o ... https://www.youtube.com/watch?v=7OzQ8ItYGSw

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=ThN1n3eJDHE