# Algorithm for determining L1 is a subset of L2.

#### zulfi100

Joined Jun 7, 2012
653
Hi,

I have a question:
Q. Show that there exist an algorithm for determining if L1 is a subset of L2 , for any regular languages L1 and L2

If L1 is a subset of L2, then according to set equality we have:

L1 is a subset of L2 and L2 is a subset of L1.

Therefore we have an algorithm according to set equality to show that L1 is subset of L2.

Some body please guide me if my argument is correct or not.

Zulfi.

#### WBahn

Joined Mar 31, 2012
26,301
No claim is being made that L1 and L2 are equal. The question is asking whether or not you can determine if one set is or is not a subset of another set.

Do you understand what it means for one set to be a subset of another set?

#### zulfi100

Joined Jun 7, 2012
653
No claim is being made that L1 and L2 are equal. The question is asking whether or not you can determine if one set is or is not a subset of another set.

Do you understand what it means for one set to be a subset of another set?
Hi,
One set S1 is a subset of another set S2 if S1 has all members same as S2 but S1 members are less than S2. So according to set theory we have an algorithm for determining if S1 is a subset of S2. But how can we show that?

Zulfi

#### WBahn

Joined Mar 31, 2012
26,301
One set S1 is a subset of another set S2 if S1 has all members same as S2 but S1 members are less than S2.
If S1 being a subset of S2 requires S1 having fewer members than S2, then how can S1 be a subset of S2 in the case that S1 is equal to S2?

So according to set theory we have an algorithm for determining if S1 is a subset of S2. But how can we show that?
How does having an algorithm for determining this follow from set theory?

#### zulfi100

Joined Jun 7, 2012
653
If S1 being a subset of S2 requires S1 having fewer members than S2, then how can S1 be a subset of S2 in the case that S1 is equal to S2?

How does having an algorithm for determining this follow from set theory?
Hi,
Regular expressions represent Finite State Machines(FSM) and FSMs follow the rules of discrete maths particularly set theory.

Zulfi.

#### WBahn

Joined Mar 31, 2012
26,301
Hi,
Regular expressions represent Finite State Machines(FSM) and FSMs follow the rules of discrete maths particularly set theory.

Zulfi.
Would you accept this as a valid response if I were to say, "According to set theory all birds have feathers," and you asked me to justify that claim?

#### zulfi100

Joined Jun 7, 2012
653
Would you accept this as a valid response if I were to say, "According to set theory all birds have feathers," and you asked me to justify that claim?
Hi,
I may ask you to show and you can show by taking clips. In set theory, we can show by using Venn Diagrams.
Is the above correct?

Zulfi.

#### zulfi100

Joined Jun 7, 2012
653
Hi,
I may ask you to show and you can show by taking clips. In set theory, we can show by using Venn Diagrams.
Is the above correct?

Zulfi.
I dont know how to show the algorithm for L1 is a subset of L2 related to set theory.

#### WBahn

Joined Mar 31, 2012
26,301
I dont know how to show the algorithm for L1 is a subset of L2 related to set theory.
Then don't make the claim!

#### zulfi100

Joined Jun 7, 2012
653
Then don't make the claim!
Then it would be wrong. Your entire set of directions would become futile.

Zulfi.

Last edited:

#### bogosort

Joined Sep 24, 2011
523
Go back to WBahn's initial question: if you're given two sets A and B, what does it mean for A to be a subset of B? (Note that we specifically used the word "subset" and not "proper subset".) Try to describe it in plain English, and then see if you can construct a simple algorithm from the description.

#### zulfi100

Joined Jun 7, 2012
653
Go back to WBahn's initial question: if you're given two sets A and B, what does it mean for A to be a subset of B? (Note that we specifically used the word "subset" and not "proper subset".) Try to describe it in plain English, and then see if you can construct a simple algorithm from the description.
https://www.mathstopia.net/sets/difference-set

Hi,
Thanks for your reply. We did some discussion on that and I provided the link on top (i.e. my question thread). So I think there should be some algorithm. I found some thing from the above link:

When a superset is subtracted from a subset, then result is an empty set, i.e, A - B = ϕ if A ⊂ B

Algorithm:
Create a superset, B
Create a subset,A
Now find A-B.
If A-B is a null set, then A is a subset of B.

Kindly correct me if I am wrong.
Zulfi.

#### bogosort

Joined Sep 24, 2011
523
Algorithm:
Create a superset, B
Create a subset,A
Now find A-B.
If A-B is a null set, then A is a subset of B.
In the part I highlighted in red, you've assumed the thing you want to prove.

I think the best approach here is to start simply, by explaining in plain English what it means for one collection of items to be a subset of another collection. To make it perfectly clear, let's define four sets:

A = { 1, 2, 3 }
B = { 1, 2, 3, 4 }
C = { 1, 2, 3 }
D = { 2, 3, 4, 5 }

Given the definitions above, the following expressions are true:
$A \subset B \\ A \subset C \\ A \not\subset D$

Using ordinary language, can you describe what makes them true?

#### zulfi100

Joined Jun 7, 2012
653
In the part I highlighted in red, you've assumed the thing you want to prove.

I think the best approach here is to start simply, by explaining in plain English what it means for one collection of items to be a subset of another collection. To make it perfectly clear, let's define four sets:

A = { 1, 2, 3 }
B = { 1, 2, 3, 4 }
C = { 1, 2, 3 }
D = { 2, 3, 4, 5 }

Given the definitions above, the following expressions are true:
$A \subset B \\ A \subset C \\ A \not\subset D$

Using ordinary language, can you describe what makes them true?
$A \subset B$ means that A has all the members 1, 2, 3 which are in B, so for all A is a member of B
$A \subset C$ means that A has all the elements 1, 2, 3 which are in C, so A is equal to C also. For all A is a member of C
$A \not\subset D$ means that A does not have all elements same as D. A is not a subset of D and for all A is not a member of D.

Thanks a lot for your guidance. What should be the next step, please?

Zulfi.

#### WBahn

Joined Mar 31, 2012
26,301
https://www.mathstopia.net/sets/difference-set

Hi,
Thanks for your reply. We did some discussion on that and I provided the link on top (i.e. my question thread). So I think there should be some algorithm. I found some thing from the above link:

When a superset is subtracted from a subset, then result is an empty set, i.e, A - B = ϕ if A ⊂ B

Algorithm:
Create a superset, B
Create a subset,A
Now find A-B.
If A-B is a null set, then A is a subset of B.

Kindly correct me if I am wrong.
Zulfi.
Your claim is: if A-B = ∅, then A ⊂ B

Your "proof" is based on the assertion that if A ⊂ B, then A-B = ∅.

You're basing your proof on the false believe that the converse of a conditional statement is valid true if the conditional statement is true.

To see this fallacy, consider the following claim (which we will assume is correct): Cars manufactured (in the U.S.) after 1968 have seat belts.

What your proof is reliant on is the converse being true which would be if a car has seat belts it was manufactured after 1968.

But lots of cars made before 1968 had seat belts -- it's just that ALL cars made after 1968 were required to have them (in the U.S.).

Also note the contradiction you have with your own previous definition of a subset. You required that the size of the subset be smaller than the size of the set (i.e., the size of A to be smaller than the size of B).

What if A and B are the same set? Then if you subtract B from A you get the empty set, but according to your definition, since A is not smaller than B, it can't be a subset of A.

#### zulfi100

Joined Jun 7, 2012
653
$A \subset B$ means that A has all the members 1, 2, 3 which are in B, so for all A is a member of B
$A \subset C$ means that A has all the elements 1, 2, 3 which are in C, so A is equal to C also. For all A is a member of C
$A \not\subset D$ means that A does not have all elements same as D. A is not a subset of D and for all A is not a member of D.

Thanks a lot for your guidance. What should be the next step, please?

Zulfi.
Hi, I have found some relationship for subset at wikepedia:
∀x(x ∈ A → x ∈ B)

Zulfi.

#### zulfi100

Joined Jun 7, 2012
653
Your claim is: if A-B = ∅, then A ⊂ B

Your "proof" is based on the assertion that if A ⊂ B, then A-B = ∅.

You're basing your proof on the false believe that the converse of a conditional statement is valid true if the conditional statement is true.

To see this fallacy, consider the following claim (which we will assume is correct): Cars manufactured (in the U.S.) after 1968 have seat belts.

What your proof is reliant on is the converse being true which would be if a car has seat belts it was manufactured after 1968.

But lots of cars made before 1968 had seat belts -- it's just that ALL cars made after 1968 were required to have them (in the U.S.).

Also note the contradiction you have with your own previous definition of a subset. You required that the size of the subset be smaller than the size of the set (i.e., the size of A to be smaller than the size of B).

What if A and B are the same set? Then if you subtract B from A you get the empty set, but according to your definition, since A is not smaller than B, it can't be a subset of A.
Hi,
I provided you the link for my assumption. I dont think that mathematically that assumption is wrong. If A is a subset of B then all A is a member of B. So A-B which is members of A not in B is false.
<
Also note the contradiction you have with your own previous definition of a subset. You required that the size of the subset be smaller than the size of the set (i.e., the size of A to be smaller than the size of B).
>
You are right, I made a mistake.

Zulfi.

#### WBahn

Joined Mar 31, 2012
26,301
Hi,
I provided you the link for my assumption. I dont think that mathematically that assumption is wrong. If A is a subset of B then all A is a member of B. So A-B which is members of A not in B is false.
You're missing the point.

The fact that "IF A ⊆ B THEN (A-B) = ∅" does not logically mean that "IF (A-B) = ∅ THEN A ⊆ B" is true. In some situations it is, but in others it is not. So no proof that is based on this premise is a valid proof.

Now, if you can show that "IF and ONLY IF A ⊆ B THEN (A-B) = ∅", then you can make the second assertion and use it as a premise in your proof.

#### bogosort

Joined Sep 24, 2011
523
$A \subset B$ means that A has all the members 1, 2, 3 which are in B, so for all A is a member of B
$A \subset C$ means that A has all the elements 1, 2, 3 which are in C, so A is equal to C also. For all A is a member of C
$A \not\subset D$ means that A does not have all elements same as D. A is not a subset of D and for all A is not a member of D.

Thanks a lot for your guidance. What should be the next step, please?
You said that $$A \subset B$$ means that all members of A are also members of B. You then found the expression ∀x(x ∈ A → x ∈ B) on Wikipedia. Can you see that both the plain language version and the Wikipedia version mean the same thing?

How can we make an algorithm from this? As a first iteration, we could try:
Code:
1. remove an element x from A
2. check if x is an element of B
2a. if x is in B, go back to step 1
2b. otherwise, stop:  A is not a subset of B
If the algorithm halts without ever reaching step 2b, then A is a subset of B.

But an algorithm, by definition, must have a finite number of steps. If A and B are infinite sets, then what we've described is not an algorithm.

Now, the real goal is to show that, if L1 and L2 are regular languages, then there exists an algorithm that can determine if L1 is a subset of L2. Since regular languages can indeed be infinite, we cannot use such a naive algorithm and must think a little more abstractly. Do you know about the closure properties of regular languages?

#### BobaMosfet

Joined Jul 1, 2009
1,229
Hi,
Regular expressions represent Finite State Machines(FSM) and FSMs follow the rules of discrete maths particularly set theory.

Zulfi.
That is not quite correct. Regex's represent automata theory- a means by identifying a pattern of data using a pattern mask that is a tokenize form allowing expansion.

An algorithm does NOT by definition have a finite number of steps. It may have a specific number of sub-processes, but how many times those processes are stepped through is not always known. Recursion is an example, and something very widely used in automata theory for regexp.

Instead of gobbledegook, why don't you simply make a flow-chart. It is the MOST logical representation of an algorithm to meet your need. Determining if one set of tokens is a subset of another set of tokens is trivial, conceptually speaking. I'm not sure why you're making it so difficult.

Something like this--

It might not be perfect, I slapped it together, on the way out the door.