Turing Machine notation: sigma-star

• Feb 8th 2010, 01:29 PM
needlittlehelp01
Turing Machine notation: sigma-star
Just clean up a minor confusion:

Often in my notes when some alphabet is being defined I see:
Sigma* or {0, 1}*

I'm afraid I've forgotten the significance of the star. Is it powersets?

(note: the notation in my notes may not be consistent with what you learnt, or what is in wikipedia or what is in some other book - that really annoys me (just makes everything seem more arbitrary) :p)

thanks
• Feb 8th 2010, 01:40 PM
clic-clac
Hi

Of course such notation depends on the author/professor, but in my courses it used to be the set of words in the considered alphabet. But that could really make sense, see how it is used.
• Feb 8th 2010, 01:56 PM
aliceinwonderland
Quote:

Originally Posted by needlittlehelp01
Just clean up a minor confusion:

Often in my notes when some alphabet is being defined I see:
Sigma* or {0, 1}*

I'm afraid I've forgotten the significance of the star. Is it powersets?

(note: the notation in my notes may not be consistent with what you learnt, or what is in wikipedia or what is in some other book - that really annoys me (just makes everything seem more arbitrary) :p)

thanks

If the notation "*" is seen in the context of Turing machine or automata theory, I think your "*" refers to a Kleen star. I am not 100% sure though. For example, $\{0,1\}^*=\{\lambda, "0", "1", "01", "10", "11", "110",...\}$, where $\lambda$ is an empty string.