For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology and operator?

The following is my understanding of the union of sets versus the concatenation of sets (Kleene star). Please correct me if I'm wrong.

Union of sets

For the two sets $\{a,b\}$ and $\{a,b\}$ we have the union \begin{align} \{a,b\}\cup\{a,b\}=\{a,b\} \tag 1 \end{align} Update: For reference I used Union (set theory) from Wikipedia.

Concatenation of sets (Kleene star)

The concatenation of $\{a,b\}$ and $\{a,b\}$ is also a union (same notation?!) of two sets \begin{align} \{a,b\}^*&=\bigcup _{i=0}^{2} \{a,b\} ^2 \tag 2\\ &=\{a,b\} \cup \{a,b\} \tag 3\\ &=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,\dots\} \tag 4 \end{align}

Update: For reference I used Kleene star from Wikipedia. And here's where my confusion lies because at Wikipedia they also use the notation with the union operator: $$ V^* = \bigcup_{i\geq 0} V^i = V^0\cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots \tag 4 $$ Which is the same (?!) notation as in my $(2) - (3)$ but with the upper bound $2$. And the notation does not coincide with $(1)$.

  • 2
    $\begingroup$ I have never seen $\cup$ used for concatenation. That would be very awkward, given the usual meaning of $\cup$. Do you have a reference? $\endgroup$ – Yuval Filmus May 22 '20 at 20:08
  • $\begingroup$ The Kleene star is the union of an infinite number of sets (if you look at it that way, which is possibly not the best way to think of it). Concatenation, on the other hand, is not a union; it's a concatenation. And I don't understand either of the equalities in the equation you show, since they are both evidently wrong. $\endgroup$ – rici May 22 '20 at 20:45
  • $\begingroup$ Hi @YuvalFilmus ! That is exactly why I'm confused. I updated with references. Feel free to clarify my misunderstanding. $\endgroup$ – JDoeDoe May 23 '20 at 6:36
  • $\begingroup$ Hi @rici ! I updated with references and numbered the equations. Feel free to correct what is wrong. $\endgroup$ – JDoeDoe May 23 '20 at 6:39
  • 1
    $\begingroup$ Wikipedia uses $\cup$ in its usual meaning, set union. $\endgroup$ – Yuval Filmus May 23 '20 at 6:52

Wikipedia is using $\cup$ in its usual meaning, set union. When Wikipedia defines $$ V^* = \bigcup_{n \geq 0} V^n = V^0 \cup V^1 \cup V^2 \cup \cdots, $$ it literally means that $V^*$ is the union of the sets $V^0,V^1,V^2,\ldots$

The concatenation happens in the definition of $V^n$, which can be defined as follows: $V^0 = \{\epsilon\}$, and $V^{n+1} = \{ xy : x \in V^n, y \in V \}$. In words, $V^n$ is the concatenation of $n$ words from $V$.


The concatenation of two sets of strings is the set formed of all pairwise concatenations of their elements. For instance, the concatenation of $\{a,b\}$ and $\{a,b\}$ is $\{a.a, a.b, b.a, b.b\}$, where $.$ is the string concatenation symbol. (Usually, we use no symbol for concatenation at all, and just write $\{aa, ab, ba, bb\}$.)

So in general, for two sets of strings $A, B$, their concatenation $AB$ is equal to $\{ xy \mid x \in A, y \in B \}$.

Now we can write

  • $A^2 = AA$ = all strings that are 2 strings from $A$ concatenated
  • $A^3 = AAA$ = all strings that are 3 strings from $A$ concatenated
  • $A^4 = AAAA$ = all strings that are 4 strings from $A$ concatenated
  • and so forth, and, for consistency,
  • $A^1 = A$ = all strings that are 1 string from $A$ concatenated
  • $A^0 = \{ \epsilon \}$ = all strings that are 0 strings from $A$ concatenated

Now the Kleene star of a set $A$ is the set $A^*$ formed by all strings consisting of arbitrarily many concatenations of strings from $A$. That is to say: such a string is

  • either 0 strings from $A$ concatenated (it is in $A^0$)
  • or 1 string from $A$ concatenated (it is in $A^1$)
  • or 2 strings from $A$ concatenated (it is in $A^2$)
  • or, ...

In other words: $\displaystyle A^* = \bigcup_{n}{A^n}$. The either ... or is where the union comes from.

You also wrote: correct me if I'm wrong. Well, you wrote this:

\begin{align} \{a,b\}^*&=\bigcup _{i=0}^{2} \{a,b\} ^2 \tag 2\\ &=\{a,b\} \cup \{a,b\} \tag 3\\ &=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,\dots\} \tag 4 \end{align}

Line (2) is just a weird way of writing $\{ a, b \} \cup \{ a, b \} \cup \{ a, b \}$. This is indeed equal to $\{ a, b \} \cup \{ a, b \}$ (3), which in turn is equal to $\{ a, b \}$. No string concatenation is going on at all here, so you're not getting any other elements than just $a$ and $b$. In (4), suddenly, you have a lot of concatenations. Clearly, that can't be right. You must have miscopied this from a source in which (2) and (3) were different.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.