[Solved]: Is $\epsilon$ always contained in $\Sigma^*$?

Problem Detail: 

Please correct me on any terminology. For some reason I'm a bit confused.

$\Sigma = \{\epsilon, 0, 1\}$

This means my alphabet, $\Sigma$, contains three symbols ($\epsilon, 0, 1$).

$\Sigma^*$ is the language over $\Sigma$, and it equals $\{\epsilon, 0, 1, 01, 10\}$.

My regular expression for $\Sigma^*$: $\epsilon+0+1+(01)+(10)$.

First question: Does every $\Sigma^*$ include $\epsilon$? I see some with, and some without. I feel like this is a big difference because your regular expression and DFSA will be different.

Second question: At this point, I would have five accepting states in a DFSA? Since the first state is the empty string, is it $\epsilon$? Or is the first state just nothing, which transitions to a second state via $\epsilon$ which contains the empty string?

Asked By : fossdeep

Answered By : David Richerby

Normally, $\epsilon$ stands for the empty string: the string with no characters, which would be "" is most programming languages. It's too confusing to have $\epsilon$ be a symbol in the alphabet, so I'm going to rename it and write your alphabet as $\Sigma=\{e,0,1\}$. (The alternative would be to use some other symbol to denote the empty string.)

Now, by definition, $\Sigma^*$ is the set of all finite strings that can be written using the characters of $\Sigma$. This always includes the empty string $\epsilon$ and, as long as $\Sigma\neq\emptyset$, it also contains strings of all finite lengths. So the claim in the question that $\Sigma^*=\{e, 0, 1, 01, 10\}$ is incorrect: $\Sigma^*$ is an infinite set.

The regular expression for $\Sigma^*$ is $(e+0+1)^*$; the automaton consists of a single state, which is accepting and has transitions to itself for each symbol in $\Sigma$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44973