What is $\Sigma\cap\Sigma^*$?

132 Views Asked by At

Let $\Sigma^*$ be set of all strings over symbols $\Sigma=\{a,b\}$. Adopting the most common definitions what is $\Sigma\cap\Sigma^*$? I'm aware that this question is ambiguous. I just wonder what the most generally accepted convention is. Is it $\varnothing$ or $\Sigma$?

1

There are 1 best solutions below

7
On

In any book of automata theory or combinatorics on words, $\Sigma$ is the alphabet and $\Sigma^*$ is the free monoid on the alphabet $\Sigma$. Let me add that $\Sigma^n$ usually denotes the set of words of length $n$, so that $\Sigma^0 = \{1\}$, the one-element set containing the empty word $1$, $\Sigma^1 = \Sigma$ and $$ \Sigma^* = \bigcup_{n \geqslant 0} \Sigma^n $$ In particular, $\Sigma$ is a subset of $\Sigma^*$ and $\Sigma \cap \Sigma^* = \Sigma$.