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?

Forumpy
 Follow
 0 followers
 6 badges
 Send a private message to Forumpy
 Thread Starter
Offline6ReputationRep: Follow
 1
 15012017 18:25

Gregorius
 Follow
 20 followers
 13 badges
 Send a private message to Gregorius
Offline13ReputationRep: Follow
 2
 16012017 10:06
(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?
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 ktuples. Let's take 3tuples 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 ktuple is that a word can be of any length whereas a ktuple is exactly k symbols long. You can, if you want, represent any string of length k as a ktuple  but since you're often interested in concatenating strings in computer science, (thus not keeping to fixed length ktuples), 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. 
 Follow
 3
 16012017 11:36
(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.
Is there some school of thought where textually repeating an element of a set makes it undefined? Confused. 
Forumpy
 Follow
 0 followers
 6 badges
 Send a private message to Forumpy
 Thread Starter
Offline6ReputationRep: Follow
 4
 16012017 13:22
(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 ktuples. Let's take 3tuples 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 ktuple is that a word can be of any length whereas a ktuple is exactly k symbols long. You can, if you want, represent any string of length k as a ktuple  but since you're often interested in concatenating strings in computer science, (thus not keeping to fixed length ktuples), 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.
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 11tuple, 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.Last edited by Forumpy; 16012017 at 13:29. 
Gregorius
 Follow
 20 followers
 13 badges
 Send a private message to Gregorius
Offline13ReputationRep: Follow
 5
 16012017 14:18
(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, is a set, but is the same as , since and , and that's really the only test we can make on a set i.e. we can ask a set, via , 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. 
Gregorius
 Follow
 20 followers
 13 badges
 Send a private message to Gregorius
Offline13ReputationRep: Follow
 6
 16012017 14:33
(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?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 11tuple, 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? 
 Follow
 7
 17012017 10:53
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 bs, 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}. 
Gregorius
 Follow
 20 followers
 13 badges
 Send a private message to Gregorius
Offline13ReputationRep: Follow
 8
 17012017 16:39
(Original post by atsruser)
(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 bs, 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}.Last edited by Gregorius; 17012017 at 16:52. 
 Follow
 9
 18012017 12:10
(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.
Reply
Submit reply
Related discussions:
 Independent Variable , Dependent Variable, Theory, and ...
 Alevel Religious Studies & Alevel Philosophy Study Group
 OCR Philosophy and Ethics Study Group (AS & A2)
 Sociology Help Thread
 Sociology help
 Further maths: is it truly that hard?!
 Taking your theory test? Read this!
 Is it possible to take just one facilitating subject & get into ...
 Illuminati/Conspiracies Real or not?
 The unlogic of the liberal left
TSR Support Team
We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.
This forum is supported by:
 SherlockHolmes
 Notnek
 charco
 Mr M
 TSR Moderator
 Nirgilis
 usycool1
 Changing Skies
 James A
 rayquaza17
 RDKGames
 randdom
 davros
 Gingerbread101
 Kvothe the Arcane
 The Financier
 The Empire Odyssey
 Protostar
 TheConfusedMedic
 nisha.sri
 Reality Check
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 LeCroissant
 EstelOfTheEyrie
 CoffeeAndPolitics
 an_atheist
 Leviathan1741
 Moltenmo
Updated: January 18, 2017
Share this discussion:
Tweet