# What does $\{$ a set $\}^{+}$ mean in the context of languages?

I came across this notation and I don't know the meaning of it, or if it's a typo: $\{$ some set $\}^{+}$

What does the + mean, i.e., the plus operator applied to a set?

• Yuval's answer is exhaustive, so I'll limit myself to a brief terminological remark. The usual $L^*$ is often called the reflexive transitive closure of $L$ under concatenation, while $L^+$ is simply the transitive closure. You can define either in terms of the other by adding or removing $\epsilon$ (or $\lambda$) to/from the generated language. For example, from Yuval's second and third examples: {a,b}$^*$ and {aa,b}$^*$ can be defined as {a,b}$^+\cup \{\epsilon\}$ and {aa,b}$^+\cup \{\epsilon\}$ respectively. And the other way around. – Hunan Rostomyan Apr 25 '14 at 6:40
• Do you mean $A^+$ or $\{A\}^+$ (for some set $A$)? That's not the same. Note that the notation is explained in any textbook on the matter, and also on Wikipedia. – Raphael Apr 25 '14 at 7:02

This is the Kleene plus. It stands for $$L^+ = \bigcup_{i \geq 1} L^i.$$ Here $L^i$ is the set of concatenations of $i$ words from $L$. In words, $L^+$ consists of all concatenations of one or more words from $L$. A related operator is the Kleene star $$L^* = \bigcup_{i \geq 0} L^i,$$ which also allows the empty string ($L^0$).
For example, if $L = \{a\}$ then $L^+ = \{a,aa,aaa,aaaa,\ldots\}$ while $L^* = \{\epsilon,a,aa,aaa,aaaa,\ldots\}$. If $L = \{a,b\}$ then $L^+ = \{a,b,aa,ab,ba,bb,aaa,\ldots\}$. If $L = \{aa,b\}$ then $L^+ = \{aa,b,aaaa,aab,baa,bb,aaaaaa,\ldots\}$.