Do(L) vs. Sq(L) - Are they Equal? Which is Regular?

Here we look at two languages Do(L) vs. Sq(L), where Do(L) is the set of strings wx where w, x are in L, and Sq(L) is the set of ww where w in L. We show that indeed these two languages are not always the same. Further, we show that Do(L) is always regular whenever L is, and Sq(L) is not always regular, even when L is.
Patreon: / easytheory
Facebook: / easytheory
Twitter: / easytheory
If you like this content, please consider subscribing to my channel: / @easytheory
▶ADDITIONAL QUESTIONS◀
1. What if L is not regular? Is Do(L) always not regular? Sq(L)?
2. For what languages L is Do(L) = Sq(L)?
▶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! Showing CFLs are closed under intersection with regular languages WITHOUT A PDA: th-cam.com/video/fiipLIVwR9o/w-d-xo.html