0
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\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 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 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 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 at 6:39
  • 1
    $\begingroup$ Wikipedia uses $\cup$ in its usual meaning, set union. $\endgroup$ – Yuval Filmus May 23 at 6:52
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.