4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Hunan Rostomyan Apr 25 '14 at 6:40
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Apr 25 '14 at 7:02
7
$\begingroup$

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\}$.

$\endgroup$
  • 2
    $\begingroup$ Outside of formal languages, the same notation is used with Cartesian product instead of concatenation. $\endgroup$ – Raphael Apr 25 '14 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy