Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    6
    ReputationRep:
    I've started an Automata module in my CS degree, and have begun learning about sets and group theory.

    I believe I understand the concept of a set and its operators, but I've now been introduced to:
    Tuples
    Pairs
    Words/Strings
    and I'm really struggling to get my head around them.

    From what I understand, all of these are 'sequences', which area list of elements in a specific order. A pair is two elements and any more is a tuple of k length.
    But I'm unsure where sets come into this. Do the elements of a set have anything to do with the elements of a sequence/tuple?

    By far the most confusing part of this to me, however, is what a word is in group theory.
    The complete definition of what a word is, given by the lecturer, is:

    "A word, or string, is a sequence of elements of arbitrary length (even zero)"

    I really don't understand what makes words/strings unique to tuples. What's the difference between a tuple and a word? The fact that it's of arbitrary length?
    Where do the elements of a word come from?
    He then went on to use words in the kleene star operation which just made matters worse. I have little to no idea what makes a word relevant to any other kind of sequence, and he's begun using it in an operation.

    None of the books he has provided mention a word or string in this context and I don't know where else to turn. It's so frustrating and confusing and I don't want to fall behind because of something as obnoxious as this.

    Can somebody please help?
    Offline

    13
    ReputationRep:
    (Original post by Forumpy)
    I've started an Automata module in my CS degree, and have begun learning about sets and group theory.

    I believe I understand the concept of a set and its operators, but I've now been introduced to:
    Tuples
    Pairs
    Words/Strings
    and I'm really struggling to get my head around them.

    From what I understand, all of these are 'sequences', which area list of elements in a specific order. A pair is two elements and any more is a tuple of k length.
    But I'm unsure where sets come into this. Do the elements of a set have anything to do with the elements of a sequence/tuple?

    By far the most confusing part of this to me, however, is what a word is in group theory.
    The complete definition of what a word is, given by the lecturer, is:

    "A word, or string, is a sequence of elements of arbitrary length (even zero)"

    I really don't understand what makes words/strings unique to tuples. What's the difference between a tuple and a word? The fact that it's of arbitrary length?
    Where do the elements of a word come from?
    He then went on to use words in the kleene star operation which just made matters worse. I have little to no idea what makes a word relevant to any other kind of sequence, and he's begun using it in an operation.

    None of the books he has provided mention a word or string in this context and I don't know where else to turn. It's so frustrating and confusing and I don't want to fall behind because of something as obnoxious as this.

    Can somebody please help?
    The basic underlying structure here is the set. A set is an unordered collection of elements that contains no repeats. So {a,b,c,d} is the same set as {b,a,c,d} and something like {a,b,b,c} is not a set.

    You then start building different structures out of the elements that are contained in sets. So ordered pairs are things of the form (x,y) where x and y are drawn from a set such as {a,b,c,d,e,f}. Notice that (a,a) is allowed and that (a,b) is distinct from (b,a).

    Then you move on to ordered k-tuples. Let's take 3-tuples as an example to be concrete: (x,y,z) where x, y and z are drawn from some set. Really no more difficult a concept that ordered pairs, just longer.

    A word or string (the terms are often taken as synonyms), is a finite sequence of symbols drawn from some alphabet. Here an alphabet is just a set of symbols. The main difference between a word and a k-tuple is that a word can be of any length whereas a k-tuple is exactly k symbols long. You can, if you want, represent any string of length k as a k-tuple - but since you're often interested in concatenating strings in computer science, (thus not keeping to fixed length k-tuples), it makes sense to use the terminology of words/strings.

    As concatenation of words/strings is so important, it makes sense to construct a structure where concatenations of strings can "live" - and this is the Kleen Star construction. Informally speaking , it's the set of all possible concatenations of words constructed out of some alphabet. The Wikipedia article is decent description of how this works.
    Offline

    11
    ReputationRep:
    (Original post by Gregorius)
    The basic underlying structure here is the set. A set is an unordered collection of elements that contains no repeats. So {a,b,c,d} is the same set as {b,a,c,d} and something like {a,b,b,c} is not a set.
    At the risk of derailing this, I feel the need to say that this looks weird to me: to my mind, A=\{a,b,b,c\} is a set, but is the same as B=\{a,b,c\}, since a,b,c \in A and a,b,c \in B, and that's really the only test we can make on a set i.e. we can ask a set, via \in, if it does or doesn't contain an element, but we can't ask if how many times it contains it.

    Is there some school of thought where textually repeating an element of a set makes it undefined? Confused.
    • Thread Starter
    Offline

    6
    ReputationRep:
    (Original post by Gregorius)
    The basic underlying structure here is the set. A set is an unordered collection of elements that contains no repeats. So {a,b,c,d} is the same set as {b,a,c,d} and something like {a,b,b,c} is not a set.

    You then start building different structures out of the elements that are contained in sets. So ordered pairs are things of the form (x,y) where x and y are drawn from a set such as {a,b,c,d,e,f}. Notice that (a,a) is allowed and that (a,b) is distinct from (b,a).

    Then you move on to ordered k-tuples. Let's take 3-tuples as an example to be concrete: (x,y,z) where x, y and z are drawn from some set. Really no more difficult a concept that ordered pairs, just longer.

    A word or string (the terms are often taken as synonyms), is a finite sequence of symbols drawn from some alphabet. Here an alphabet is just a set of symbols. The main difference between a word and a k-tuple is that a word can be of any length whereas a k-tuple is exactly k symbols long. You can, if you want, represent any string of length k as a k-tuple - but since you're often interested in concatenating strings in computer science, (thus not keeping to fixed length k-tuples), it makes sense to use the terminology of words/strings.

    As concatenation of words/strings is so important, it makes sense to construct a structure where concatenations of strings can "live" - and this is the Kleen Star construction. Informally speaking , it's the set of all possible concatenations of words constructed out of some alphabet. The Wikipedia article is decent description of how this works.
    This is fantastic. Thank you so much.
    I have some further questions however.

    Do sequences/tuples/pairs etc need to come from some set originally?

    When you say "A word is a finite sequence of symbols", does that essentially mean that its length is not known or not relevant?
    So for instance, "abracadabra" could be seen as a 11-tuple, but for the purposes of concatenation, its exact length is not important?

    And finally, regarding the Kleene Star operation, is this the set of all possible concatenations? It doesn't have an order?
    How long is a product of a Kleene Star operation? Is it infinite? I've seen examples where they show (0,1)* as {0,1,00,11,0101,0011...}. Is it finite or does its length not matter?
    And also, why is this useful?

    Thank you so much for your help. You've worded it in an understandable way.
    Offline

    13
    ReputationRep:
    (Original post by atsruser)
    At the risk of derailing this, I feel the need to say that this looks weird to me: to my mind, A=\{a,b,b,c\} is a set, but is the same as B=\{a,b,c\}, since a,b,c \in A and a,b,c \in B, and that's really the only test we can make on a set i.e. we can ask a set, via \in, if it does or doesn't contain an element, but we can't ask if how many times it contains it.

    Is there some school of thought where textually repeating an element of a set makes it undefined? Confused.
    Perhaps take a look here.
    Offline

    13
    ReputationRep:
    (Original post by Forumpy)
    This is fantastic. Thank you so much.
    I have some further questions however.

    Do sequences/tuples/pairs etc need to come from some set originally?
    Depends on what you mean by "need to" ! The usual formalism that is used starts off from the idea of a set of elements. Indeed, in a slightly more formal treatment, pairs and tuples are defined in terms of the Cartesian product of sets. Going this way makes things nice and clean. I expect (not having thought about this) that if you start off with some primitive notion of "pairs", you could recover the idea of a set from projection on either factor.

    When you say "A word is a finite sequence of symbols", does that essentially mean that its length is not known or not relevant?
    So for instance, "abracadabra" could be seen as a 11-tuple, but for the purposes of concatenation, its exact length is not important?
    Yes. This idea of word or string removes the constraint of fixed length and allows you to freely use the concatenation operator and stay within the structure you started off with.

    And finally, regarding the Kleene Star operation, is this the set of all possible concatenations? It doesn't have an order?
    It is a set, but it is a set of objects that themselves have an order. Think about a simple example like {ab, ba}. This set has two elements which are words of length two; ab is not the same as ba as order matters for them. But as far as the containing set is concerned, {ab, ba} = {ba, ab}. Does that help?

    How long is a product of a Kleene Star operation? Is it infinite? I've seen examples where they show (0,1)* as {0,1,00,11,0101,0011...}. Is it finite or does its length not matter? And also, why is this useful?
    Yes, it is an infinite set. The point of it is that removes any restriction on the length of strings that you can use, when you're interested in using the concatenation operator.. If you were to restrict your set to strings of length 235 or less, then concatenating two strings of length 200 would give you something not contained in your set. Removing the length restriction gives you the generally desirable property of "closure" under the operation (concatenation) that you are interested in.
    Offline

    11
    ReputationRep:
    (Original post by Gregorius)
    Perhaps take a look here.
    I'm familiar with multisets - in fact, many years ago, I wrote a software implementation of a multiset (in C, mind, the manly way - none of this C++ standard lib nonsense). However, my question didn't have much to do with multisets. I was querying your assertion that "something like {a,b,b,c} is not a set".

    The only way that makes sense to me is to interpret it as saying "if you insist that the object {a,b,b,c} is a meaningful object, containing 2 distinct b-s, then it can't be a set". In which case, I agree, but I also think the expression {a,b,b,c} is a perfectly good set - it just happens to be the same set as {a,b,c}.
    Offline

    13
    ReputationRep:
    (Original post by atsruser)
    (in C, mind, the manly way - none of this C++ standard lib nonsense).
    Bravo!

    However, my question didn't have much to do with multisets. I was querying your assertion that "something like {a,b,b,c} is not a set".

    The only way that makes sense to me is to interpret it as saying "if you insist that the object {a,b,b,c} is a meaningful object, containing 2 distinct b-s, then it can't be a set". In which case, I agree, but I also think the expression {a,b,b,c} is a perfectly good set - it just happens to be the same set as {a,b,c}.
    Understood. Key here is what those curly braces mean and what you are allowed to put in them. I follow the convention I was taught that the curly braces denote that you are going to list the elements of a set (or multiset). As as set has to have distinct elements, a listing of elements thence distinguishes between a set and a multiset.
    Offline

    11
    ReputationRep:
    (Original post by Gregorius)
    Understood. Key here is what those curly braces mean and what you are allowed to put in them. I follow the convention I was taught that the curly braces denote that you are going to list the elements of a set (or multiset). As as set has to have distinct elements, a listing of elements thence distinguishes between a set and a multiset.
    OK, I understand what you mean now - I guess if you use multisets then it's useful to overload the meaning of the braces like this (though why not just invent a standard notation?) - I've never used multisets in any real mathematical way though, so it strikes me as slightly odd.
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    What newspaper do you read/prefer?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.