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 $Sigmaneqemptyset$, 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
