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$

closed as off-topic by D.W. Jan 20 '17 at 4:42

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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