# What is the best way to prove (S+)+ = S+? [closed]

Lets say I have the below language:

S = {a, b}


So if we apply Kleene plus to that language, it is something like:

S+ = {a, b, aa, bb, ... ..}


If we apply Kleene plus to above language again, It is something like:

(S+)+ = {a, b, aa, bb, aaa, bbb ... ..}


What are the best words/way to describe that (S+)+ = S+?

Obviously, S+ is all concatenations of words in S excluding the /\ (the empty string)

In this case, (S+)+ is all concatenations of words in S+ excluding /\

So that means (S+)+ includes the words in S+. Is this a good proof?

• I know nothing about formal languages, but I think the usual proof strategy here would be to consider an arbitrary word $x$ in S+ and show that it is in (S+)+ (this establishes that S+ $\subseteq$ (S+)+), and then to consider an arbitrary word $y$ in (S+)+ and show that it is in S+ (establishing that (S+)+ $\subseteq$ S+, which together with S+ $\subseteq$ (S+)+, implies S+ = (S+)+). – j_random_hacker Jan 20 '17 at 2:37
• Cross-posted: math.stackexchange.com/q/2105480/14578, cs.stackexchange.com/q/69009/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Jan 20 '17 at 4:12
• I'm voting to close this question because it was cross-posted on Math.SE. – D.W. Jan 20 '17 at 4:42
• As you say, S+ contains ALL the catenations of words in S. The words in S++ are catenations of words in S+, which in turn are catenations of words in S. thus also the words in S++ are catenations of words in S. This shows (S+)+ ⊆ S+, the reverse holds by definition. – Peter Leupold Jan 20 '17 at 11:27