[eZACKe]

I have this problem for my Theory of Computation class:

Prove or disprove (L1 ∪ L2)^R = L1^R ∪ L2^R for all languages L1 and L2.

Note: The R superscript stands for "reverse".

Now, I'm not the best at proofs which is why I'm coming here. I "think" I've figured it out, but it just seems to easy. I feel like I must be missing something, or I'm assuming something that isn't actually valid in this scenario.

This is what I have:

The left side of the equation says (L1 ∪ L2)^R. By DeMorgan's we know this is equal to L1^R ∩ L2^R.

However, the right side implies that this equals L1^R ∪ L2^R. This is incorrect due to DeMorgan's. Disproved.


Is it really this simple? Does DeMorgan's apply to languages like this? If I'm thinking about this completely wrong could someone get me on the right track?

Thank you!

This post has been edited by eZACKe: 03 February 2011 - 01:00 PM

[Nikitin]

Where did you get that DeMorgan law from? It's obviously false, but just wanted to see the reasoning behind that.

Yes, about putting you on the right track, write down in set-builder notation what the set (L1 ∪ L2) stands for. Then write down what the set (L1 ∪ L2)R is.

This post has been edited by Nikitin: 03 February 2011 - 02:49 PM

[Dogstopper]

It's one of the first laws you get in computer science. I learned it AP Comp Science, and it was the only law that was required to know in there.

[Nikitin]

Dogstopper, on 03 February 2011 - 03:48 PM, said:

It's one of the first laws you get in computer science. I learned it AP Comp Science, and it was the only law that was required to know in there.

The one that OP is using, and the one that I'm referring to? That "law" is clearly false.

[Dogstopper]

Oh yah.

DeMorgans's law says this:

!(a && B) == !a || !b
and
!(a || B) == !a && !b

[Nikitin]

Might as well use the set version of it. But yeah, what about it?

[eZACKe]

Just looked at it too fast I guess and saw DeMorgan's.

So let me see:

You're saying:
{x ∈ L : x ∈ L1 or x ∈ L2}
I'm not exactly sure how to write something like (L1 ∪ L2)^R in set-builder though.

This is my thought process:
This is saying {x ∈ L : x ∈ L1 or x ∈ L2}
-x is in a language L such that x is in L1 or in L2.

If all that is to the R, then it's saying:
-x is in the reverse of language L such that x is in the reverse of L1 or in the reverse of L2.

Am I right about the bottom one?

If so, that's it right?

Thanks for the help. Sorry, I'm bad at this stuff.

[Nikitin]

Your definition for (L1 ∪ L2) is correct.

Now, here's how the reversal operation is defined for a language L.

L^R = {w^r | w ∈ L}

Would you agree? We're just reversing all the strings in L.

Apply that definition to the union of languages (which itself is just a single language).

This post has been edited by Nikitin: 03 February 2011 - 03:16 PM

[eZACKe]

Actually new thought process:

(L1 ∪ L2)^R

So you start with 2 "sets" which are the two languages, L1 and L2.

You take the union of them which gives you everything that is not mutual. You then take the reverse of this new set I'll call it L3.

Now we're asking is L3 the same as L1 reversed and L2 reversed then take the union of that to get a new language I'll call L4.

Example:

L1 = abce
L2 = abcd

union of them is ed. Reverse is de. So that's the left side.

L1 reverse is ecba
L2 reverse is dcba

union of them is ed. Reverse is de. So that's the right side.

They are equal.

That's right, right?

Just not exactly sure how to say that in a "mathy" way.


EDIT: Yeah, I think we're saying the same thing now, right?

This post has been edited by eZACKe: 03 February 2011 - 03:20 PM

[Nikitin]

eZACKe, on 03 February 2011 - 04:19 PM, said:

You take the union of them which gives you everything that is not mutual.

That's not what union does. Didn't follow you after that. Why not just stick to the straightforward way of proving the equality of sets - showing that they represent the same conditions? That should be mathy enough.

[eZACKe]

(L1 ∪ L2) = {x ∈ L : x ∈ L1 or x ∈ L2}
Let (L1 ∪ L2) = L3

L3^R = {w^r | w ∈ L3} <-left side

L1^R = {w^r | w ∈ L1}
L2^R = {{w^r | w ∈ L2}

L4 = L1^R ∪ L2^R


So this is what is going on as an example:
Left Side: {1,2,3}∪{4,5,6} = 123456^R = 654321
Right Side: {1,2,3}^R = 321
{4,5,6}^R = 654

321 ∪ 654 = 321654 != 654321

Now I know I'm missing something in the top proof that shows this, but I can't figure out how to throw it in there to actually show it for all languages.

[Nikitin]

eZACKe, on 03 February 2011 - 04:33 PM, said:

(L1 ∪ L2) = {x ∈ L : x ∈ L1 or x ∈ L2}
Let (L1 ∪ L2) = L3

L3^R = {w^r | w ∈ L3} <-left side

Stop there. Why not expand the L3 into (L1 ∪ L2)? Since that's the set whose reversal you want to look at.

This post has been edited by Nikitin: 03 February 2011 - 03:37 PM

[eZACKe]

Expand it into (L1 ∪ L2)? Didn't I just take it from that though?

But: L3 = {x : x ∈ L1 or x ∈ L2}
Is this what you mean?

L3^R = {w^r : w ∈ L1 or w ∈ L2}

= w^r ∪ w^r

------------------------------------

L1^R = {w^r | w ∈ L1}
L2^R = {w^r | w ∈ L2}

= w^r ∪ w^r

-------------------------
w^r ∪ w^r = w^r ∪ w^r

Something like this?



So this is what I have down right now:

Let L3 = (L1 ∪ L2)
L3 = {x | x ∈ L1 or x ∈ L2}
L3^R = {w^r | w ∈ L1 or w ∈ L2}
= w^r ∪ w^r
--
L1^R = {w^r | w ∈ L1}
L2^R = {w^r | w ∈ L2}
L1^R ∪ L2^R = w^r ∪ w^r
--
w^r ∪ w^r = w^r ∪ w^r

This post has been edited by eZACKe: 03 February 2011 - 04:25 PM

[Nikitin]

I need to leave, but here's a solution. Go over it and see that all I'm doing is using the definition for the union and the reversal operations. You're trying to invent new stuff, when all it is, is just treating (L1 ∪ L2) as a single language and applying the previous definitions to it.


(L1 ∪ L2) = {x : x ∈ L1 or x ∈ L2}
L^R = {x^R : x ∈ L}

(L1 ∪ L2)^R = {x^R : x ∈ (L1 ∪ L2)} #definition of reversal
= {x^R : x ∈ L1 or x ∈ L2} #definition of union
= {x^R : x ∈ L1} ∪ {x^R ∈ L : x ∈ L2} #definition of union
= L1^R ∪ L2^R #definition of reversal

This post has been edited by Nikitin: 03 February 2011 - 04:38 PM

[eZACKe]

Thank you.

I need some practice.