Which of these languages is regular? Surprising answer!

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: / easytheory
Facebook: / easytheory
Twitter: / easytheory
If you like this content, please consider subscribing to my channel: / @easytheory
▶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◀
[e-mail]
▶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 TH-cam 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 course, challenging.
But to show something is impossible is rare in computer
science, and very humbling.

[@EasyTheory]

Next video! NFA to DFA (Powerset construction) th-cam.com/video/jMxuL4Xzi_A/w-d-xo.html

[@abhishekkumar-ef1xj]

i have some doubt here . You define L0,01 as every string without 00 as substring . so from right hand side 10 is acceptable as it don't have 00 as substring but it will not come under L0,01 so i thing RHS expression is wrong or if i am missing anything please clarify

[@EasyTheory]

Hi Abishek. You're right! My mistake. The actual language should be all the strings that, for every 0 in the string, a 1 appears right after it. So the regex for it would be (01 U epsilon)1*(011*)*, I think.

[@SamathaGone]

Interesting 😊

[@HelloThere-xs8ss]

Idk and tbh, covid has me not caring anymore. Can regular languages grow food that we'll need when shtf? No? Okay, keeping my priorities straight.

[@EasyTheory]

Unbelievably, yes! This morning I worked the farm and found a growing pumping length and baked with it! Good times, good times.

[@HelloThere-xs8ss]

@@EasyTheory yes