Proving two languages equality

[M_t_set]

Hello!
First of all I'm sorry if this is not the correct thread to post this I'm new here! This is the exercise:

Given two languages L and M prove that: L*M U M= L*M

I'm thinking of saying that we can write

M={empty word}M =L⁰M​

If we replace M in L*MU M we get

L*M U L⁰M = L*M
​

Is this right and enough? Can I do everything I mentioned?

 

[Dr.Peterson]

It would be helpful to state the context, since this is a specialized topic that few (if any) of us may be immediately familiar with.

What course is this for? How are you defining "language", and the operations you are applying? Are there any theorems you could apply? Perhaps a link to a source would be good, so we don't have to look it up ourselves.

 

[M_t_set]

It would be helpful to state the context, since this is a specialized topic that few (if any) of us may be immediately familiar with.

What course is this for? How are you defining "language", and the operations you are applying? Are there any theorems you could apply? Perhaps a link to a source would be good, so we don't have to look it up ourselves.

Hey thank you fo the reply!
I will edit this after I respond you, hopefully it will be more complete.

I'm taking a class in Discrete Mathematics where we are studying formal languages.
The definition of formal languague, from wikipedia pardom me, is "a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules." L and M are essential sets of words that satisfy those two abstract languages, since this is theorical math the point is to prove that is true no matter what languague L and M are.
My teacher asked us if the property L*M U M= L*M is true and how can we prove it if so.
There isn't a lot more information as this is theorical but hope it makes a bit more sense...

 

[M_t_set]

Since L and M are sets basic set operations work here .
Also the * is the kleene star so:

L*= sum L^i for i>=0​

And L^0={empty word} (this is always true for any formal languague)
In formal languages the empty word is represented by epsilon but I'm not sure of how to do it here.

Hope this helps a bit more into understanding the problem

 

[Dr.Peterson]

Thanks. I've never studied this topic specifically, so if someone else already knows it, I hope they'll answer you. I'll just continue clarifying details for the moment. I found the topic in the last chapter of a Discrete Math book I have, so I'll go by that, since you didn't fully explain the details.

The problem is,

Given two languages L and M prove that: L*M U M= L*M​

I had assumed * was a binary operation, from the way this is written; but I see it is a unary operation, the Kleene closure, namely the language that consists of all finite concatenations of strings (words?) in a language. The binary operation indicated by juxtaposing language names is "concatenation", which you didn't mention; it's the language consisting of concatenations of strings in each language (in order). So "L*M" is actually L* M, the concatenation of the Kleene closure of L with M. So I would start by thinking through what this means, and then what it means to take the union of this with M itself.

(I'll admit that I could have just looked this up, but wanted to give you the opportunity to practice explaining it to someone else, which is important in learning something well, and might even have led to your answering your own question.)

Now, you said,

I'm thinking of saying that we can write

M={empty word}M =L⁰M​

If we replace M in L*M U M we get

L*M U L⁰M = L*M​

The first statement is true, and I presume you have theorems that support it; the second superficially looks plausible, but you haven't said why you think it is true. Again, do you have any theorems about how the union of languages works? Or are you applying a theorem about union of sets? You'll just need to support your claim by some sort of reasoning. It will probably not require much, but it does require something!

(You could use "[ MATH ] \epsilon [ MATH ]", with the spaces removed, to insert an epsilon, or just paste it in from another source.)

 

[M_t_set]

Thanks. I've never studied this topic specifically, so if someone else already knows it, I hope they'll answer you. I'll just continue clarifying details for the moment. I found the topic in the last chapter of a Discrete Math book I have, so I'll go by that, since you didn't fully explain the details.

The problem is,

Given two languages L and M prove that: L*M U M= L*M​

I had assumed * was a binary operation, from the way this is written; but I see it is a unary operation, the Kleene closure, namely the language that consists of all finite concatenations of strings (words?) in a language. The binary operation indicated by juxtaposing language names is "concatenation", which you didn't mention; it's the language consisting of concatenations of strings in each language (in order). So "L*M" is actually L* M, the concatenation of the Kleene closure of L with M. So I would start by thinking through what this means, and then what it means to take the union of this with M itself.

(I'll admit that I could have just looked this up, but wanted to give you the opportunity to practice explaining it to someone else, which is important in learning something well, and might even have led to your answering your own question.)

Now, you said,

The first statement is true, and I presume you have theorems that support it; the second superficially looks plausible, but you haven't said why you think it is true. Again, do you have any theorems about how the union of languages works? Or are you applying a theorem about union of sets? You'll just need to support your claim by some sort of reasoning. It will probably not require much, but it does require something!

(You could use "[ MATH ] \epsilon [ MATH ]", with the spaces removed, to insert an epsilon, or just paste it in from another source.)

Hey again!
Thank your for all the help. I do sometimes get a bit lazy in explanations, I had a course last year on this topic as well, but more connected with graphs and computer science so I feel a bit tired of the topic I'm sorry for the small explanations.

(For someone that never studied this topic you grasped it very well, rather good explanation)

Well I shall stop being lazy and fully explain what I'm thinking :'p

1. M={ε}M because here ε is an empty string/word so attaching it to any word of M is not going to change anything, ie ε is the identity in concatenation​
2. L⁰={ε} if you look for the definition of power languages you realise that this happens with every language
   little more info that doesn't matter but I hope it makes it a bit more fun for you and perhaps makes you want to study more of this. In fact "the languague empty set" raised to power 0 is also {ε}. So if you take the kleene closure for the empty set={ε}. When I started to learn more of this I would have guessed that the kleene closure of the empty set would have been an empty set as well but it isn't!​
3. From 1 and 2 we take M=L⁰M​
4. Replace M in L*M U M= L*M U L⁰M
   Note that L*M= U LⁱM for i>=0 meaning L*M=L⁰M U L¹M U L²M U...​
5. So indeed my last idea was to use simple set rules.
   L*M U L⁰M = L*M​

Hope it makes even more sense please tell me what you think.

 

[Dr.Peterson]

Thanks. Since the goal is a proof, there are two phases to your work: first thinking informally about how the proof might work (which I think is what you expressed "lazily" to start with, which can be fine); and then writing it formally so that every step is justified by a definition, axiom, or theorem. That's where I've been pressing you to be precise, because I can only tell if you've got a proof when I see that.

Now, it appears that the "simple set rules" you are appealing to include something like (A U B) U B = A U B. You will want to state precisely what that rule is, because this is a proof, right?

But I'm a little concerned there, because I happen to know that infinite unions (or infinite anything) can be slippery, so if you only have a "rule" about finite unions, you can't apply it quietly to an infinite union and expect a mathematician to give you a pass.

So, what theorem are you using?

(I'll tell you that my first thought on this problem was not to use an infinite union (which is not mentioned in the two pages my book spends on these ideas), but to try to show that any word in L*M U M is in L*M, and vice versa.)

 

[M_t_set]

Yes you are right I think doing this is a bit risky and "abusive".

I think I will state that M={ε}M then using distribuition L*M U {ε}M= (L* U {ε})M since {ε} is in L* we have that that equals to L*M.

I had the exact first thought but then I started doing these and know I wanted to finnish it.

Let me know what do you think of this solution now.

 

[Dr.Peterson]

I think this is right, but if you haven't been given a theorem about concatenation distributing over union, that is, LM U NM = (L U N)M, you will have to prove it. I don't think that's hard to do.