1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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+)+). $\endgroup$ – j_random_hacker Jan 20 '17 at 2:37
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 20 '17 at 4:12
  • $\begingroup$ I'm voting to close this question because it was cross-posted on Math.SE. $\endgroup$ – D.W. Jan 20 '17 at 4:42
  • $\begingroup$ 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. $\endgroup$ – Peter Leupold Jan 20 '17 at 11:27