How to prove if Language L1 is equal to Language L2

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Checking if L1==L2.jpgHi,
I want to proof if L1 is equal to L2. I found a slide related to that. However, I can't understand two things, I have represented with (1) and (2) in the attached image
(1) Initially we started with (L1 intersection L2') U (L1' intersection L2) = phi but in the next step it was changed to:

(L1 intersection L2') and (L1' intersection L2) = phi , I can't understand this. We could have started with: (L1 intersection L2') and (L1' intersection L2) = phi
(2) In (2) L1 intersection L2' was removed with circles showing L1 subset of L2 and after the circles we have L2' and similarly in the next part of that line we have: L1' intersection L2 was removed with circles showing L2 subset of L1 and after the circles we have L1'.

Somebody please explain me the (1) & (2) points?

I dont have any argument for (1) but for (2) I can say that we have something like this if we convert the circles in mathematical notation:
L2. L2' and L1.L', both of them are equal to phi but in the next line they are writing L1 is a subset of L2 and L2 is a subset of L1.

Zulfi.
 

bogosort

Joined Sep 24, 2011
696
(1) Initially we started with (L1 intersection L2') U (L1' intersection L2) = phi
NB: the symbol of the slashed circle is NULL, not phi. In set theory, NULL is taken to represent the empty set, e.g., the intersection of a set with its complement.

The first panel suggests that if you can show that the union of the set (L1 AND ~L2) with (~L1 AND L2) is empty, then the sets L1 and L2 must be equal.

The second panel goes on to do just that. We know that the union of two sets is empty if and only if both sets are empty, so the task is to see if each side of the union is empty.

On the panel's left, the set (L1 AND ~L2) is considered. The Venn diagram shows that the expression "(L1 AND ~L2) = NULL" is equivalent to the expression "L1 is a subset of L2". Do you see why?

A similar argument is made on the right side: if (~L1 AND L2) is empty, then L2 is a subset of L1.

By definition of set equality, set A equals set B if and only if A is a subset of B and B is a subset of A. Given the assumption that the union of (L1 AND ~L2) with (~L1 AND L2) is empty, we have that L1 is a subset of L2 and L2 is a subset of L1. Therefore, L1 and L2 must be equal if that particular union is empty.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
NB: the symbol of the slashed circle is NULL, not phi. In set theory, NULL is taken to represent the empty set, e.g., the intersection of a set with its complement.

The first panel suggests that if you can show that the union of the set (L1 AND ~L2) with (~L1 AND L2) is empty, then the sets L1 and L2 must be equal.

The second panel goes on to do just that. We know that the union of two sets is empty if and only if both sets are empty, so the task is to see if each side of the union is empty.

On the panel's left, the set (L1 AND ~L2) is considered. The Venn diagram shows that the expression "(L1 AND ~L2) = NULL" is equivalent to the expression "L1 is a subset of L2". Do you see why?

A similar argument is made on the right side: if (~L1 AND L2) is empty, then L2 is a subset of L1.

By definition of set equality, set A equals set B if and only if A is a subset of B and B is a subset of A. Given the assumption that the union of (L1 AND ~L2) with (~L1 AND L2) is empty, we have that L1 is a subset of L2 and L2 is a subset of L1. Therefore, L1 and L2 must be equal if that particular union is empty.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your reply.

I can't understand why have you replaced 'intersection' with 'AND'. I got some . I have still confusion with Ven Diagram in setp 3 which I called (2):

Is Step#2 in slide 2 (i.e. on the right) equal to Venn Diagram in Step3??

Step#4 says (L1 is a subset of L2). How we got rid of ~L2(i.e complement of L2) in step#4?

Some body please guide me.
Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
Intersection and logical AND go hand in hand in set theory.

Think of a couple of sets that you can easily picture the relationships.

For instance, Set 1 is the set of all animals that reproduce by laying eggs (so it includes all birds, but also most reptiles, lots of fish, and a few mammals.

Now take Set 2 to be all animals that breath underwater. This includes all fish, but lots of other animals as well.

The intersection of these two sets therefore consists of all animals that are in Set 1 AND in Set 2. Do you see how the word AND naturally implies intersection when talking about sets?

Similarly, the union of these two sets consists of all animals that are in Set 1 OR Set 2, so the work OR implies union when talking about sets.

The logic that L1 intersected with the complement of L2 yields the empty set implies that L1 is a subset of L2 is pretty straight forward.

If L1 and (L2)' have nothing in common, then each member of L1 is not a member of (L2)'

Any item that is not a member of (L2)' must, by definition, be a member of L2 since the definition of the complement of a set is each and every member that is not a member of that set.
 

WBahn

Joined Mar 31, 2012
29,976
I want to proof if L1 is equal to L2. I found a slide related to that.
One thing to keep in mind is that this is just one way to prove that two regular languages are equivalent. It is based on the general notion of showing that two sets are equal if you can show that each set is a subset of the other (i.e., that each member of each set is a member of the other set).

For regular languages specifically you have a couple of other tools. First, you can come up with the minimal DFA that recognizes each and then show that the two DFAs are identical since the minimal DFA for any regular language is unique. In principle you could also come up with a regular expression for each language and then show that these are equivalent expressions; however this is trickier because there is no standard representation for regular expressions and so getting them both into the same form is an art (whereas working with the DFAs is purely algorithmic).
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks a lot for explaining me all this in a very nice manner. I can't understand why we have L2' and L1' after the Venn diagram.

Zulfi.
 

bogosort

Joined Sep 24, 2011
696
I can't understand why we have L2' and L1' after the Venn diagram.
If we denote L2 as a circle -- implying that every element of L2 is inside the circle -- then its complement ~L2 must include everything outside the circle. This makes sense, yes? So, we draw a circle with the symbol "L2" inside of it, and outside the circle we draw the symbol "~L2". Not shown in your image is an implied rectangle around both L2 and ~L2, which represents the "universal set" U (aka the domain of discourse), which contains every set that we're presently considering. You should be able to see that ~L2 is precisely equal to the set difference U - L2. In other words, if you take every element that belongs to L2 out of U, you're left with ~L2.

Now, the question is where to draw the L1 circle. If L1 and ~L2 are disjoint -- i.e., they share no common elements: (L1 AND ~L2) = NULL -- then we have only one choice: inside the L2 circle. We can't put it outside the L2 circle because that would mean that L1 shares at least one element with ~L2, but we said they were disjoint. Therefore, since L1 is within the L2 circle, it must be a subset of L2. This is what the Venn diagrams are describing.

As an example, suppose that our domain of discourse is the first ten positive integers, with L1 = { 1, 2 } and L2 = { 1, 2, 3, 4 }. Then, ~L2 = { 5, 6, 7, 8, 9, 10 }. It's easy to see that L1 is a subset of L2, that (L1 AND ~L2) is the empty set, and that both statements imply each other.
 
Top