Strings that are not substrings but are subsequences...WHAT?!

preview_player
Показать описание
Here we look at the language of all strings within a regular language L that, given a finite language L', (1) no string in L contains a substring that is a string in L', and (2) for each string in L', it is a sub*sequence* of a string in L. The goal is to show the resulting language is regular.

Yes, I know it sounds complicated, but the idea is very simple. We just show that (1) and (2) are regular, and then the result is regular. For both we make regular expressions that allow us to conclude that each is regular. Because L' is finite, even though (2) seems more complicated, it is very easy to make a regular expression for it.

▶ADDITIONAL QUESTIONS◀
1. What if L' were infinite?
2. What if we wanted the strings that are either in (1) or (2), but not both?

▶SEND ME THEORY QUESTIONS◀

▶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 course, challenging.
But to show something is impossible is rare in computer
science, and very humbling.
Рекомендации по теме
Комментарии
Автор

Not able to get the explanation of (1)

We needed such string in L' such that no string of this language is a substring of any w (that belongs to) L

First what we did, is that we made another language let us call it P. Here we included those strings which are a substring of any w that belongs to L. Right?

Now we can form a language that will include strings in P as a substring, let's call this Q. By using regex and concatenation.

And taking a complement of this Q, will get us all this strings which do not include where any string of P acts a substring in Q. But here you wrote that "all strings in sigma* that contain something in L' as a substring", wouldn't this be opposite?

Or, I'm just moving to the wrong direction and interpreted it all wrong

real-investment-banker