Empty String vs Empty Set - The Beard Sage

A set is a collection of objects. It can be visualized as a container holding some elements. If the container happens to be empty it is equivalent to having an empty set. Strings are defined over an alphabet as a finite sequence of symbols. A string of length zero is equivalent to an empty string.

Empty String

The empty string is a string of zero length. If its length is zero there should be a special way to express it. In programming, the following syntax defines an empty string

empty = ''

However, this terminology is not used while defining strings over an alphabet. A cleaner approach is to define the empty string using the symbol $\epsilon$ . Note that, the empty string is not an alphabet symbol. It merely denotes the fact that it is the absence of any symbol.

$\begin{equation*}$\epsilon \notin \Sigma$\end{equation*}$

An easy trick to clear this concept is to read $\epsilon$ as the absence of any symbol instead of reading it as another symbol. This understanding leads to the following results

$\begin{equation*}$\epsilon \cdot \epsilon = \epsilon$\end{equation*}$

$\begin{equation*}$\epsilon \cdot \Sigma = \Sigma \cdot \epsilon = \Sigma$\end{equation*}$

$\begin{equation*}$\epsilon \cup \Sigma = \Sigma \cup \epsilon$\end{equation*}$

The last term is sometimes abbreviated as $\Sigma_{\epsilon}$ .

Empty Set

The empty set is a collection of zero elements. It is represented by the symbol $\emptyset$ . Mathematically,

$\begin{equation*}$\emptyset = \{\}$\end{equation*}$

Taking a union of a set with the empty set results in the set itself. This is because the empty set does not add any new elements to the result.

$\begin{equation*}$\emptyset \cup \Sigma = \Sigma \cup \emptyset = \Sigma$\end{equation*}$

However, performing a concatenation with the empty set results in an empty set. This is because one half of the result needs to come from an element of the empty set of which there are none.

$\begin{equation*}$\emptyset \cdot \Sigma = \Sigma \cdot \emptyset = \emptyset$\end{equation*}$

Kleene Star

The star operator is the set of all strings obtained by concatenating 0 or more occurrences of the operand. 0 occurrences of anything is basically an empty string. Thus,

$\begin{equation*}$\emptyset^* = \{\epsilon\}$\end{equation*}$

$\begin{equation*}$\epsilon^* = \{\epsilon\}$\end{equation*}$

2 Comments → Empty String vs Empty Set

Pingback: Converting a Regular Expression to an equivalent NFA - TheBeardSage
Matteo August 30, 2021 at 11:48 am

Thank you so so much, dear TheBeard.
I really needed to have confirm for the equivalence between epsilon and epsilon star.

Unfortunately for Informatics Fundamentals there are no topics in internet, you are the only one who posted something about it. Thank you.

Reply ↓

Empty String

Empty Set

Kleene Star

2 Comments → Empty String vs Empty Set

Leave a Reply Cancel reply