patternMinor
What does $\{$ a set $\}^{+}$ mean in the context of languages?
Viewed 0 times
thewhatlanguagesmeandoescontextset
Problem
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?
What does the + mean, i.e., the plus operator applied to a set?
Solution
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\}$.
$$ 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\}$.
Context
StackExchange Computer Science Q#24094, answer score: 7
Revisions (0)
No revisions yet.