Algorithm for determining L1 is a subset of L2.

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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.
https://forum.allaboutcircuits.com/...f-language-l1-is-equal-to-language-l2.164158/

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

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
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?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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,
Thanks for your response.
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
29,976
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?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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,
Thanks for your reply.
Regular expressions represent Finite State Machines(FSM) and FSMs follow the rules of discrete maths particularly set theory.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
Hi,
Thanks for your reply.
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?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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.
 

bogosort

Joined Sep 24, 2011
696
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.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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
696
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?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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
29,976
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.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
\[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.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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
29,976
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
696
\[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
2,110
Hi,
Thanks for your reply.
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--

1573075299616.png

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

Barring that, there's likely something already here_ your question's already been done by some developer:

Title: Algorithms in C, 3rd Ed. [Parts 1-4, Fundamentals, Data Structures, Sorting, Searching]
Author: Robert Sedgewick
ISBN: 0-201-31452-5
 
Last edited:
Top