Results 1 to 3 of 3

Math Help - Turing Machine notation: sigma-star

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    5

    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) )

    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by needlittlehelp01 View Post
    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) )

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Turing machine notation for not on multiple symbols
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 25th 2011, 12:44 PM
  2. Can a Turing Machine(TM) know what square its at ?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 17th 2011, 10:41 AM
  3. Turing Machine
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2010, 06:39 AM
  4. LOOP Turing machine
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 24th 2010, 04:15 PM
  5. Turing machine
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: August 21st 2010, 07:17 AM

Search Tags


/mathhelpforum @mathhelpforum