1

Let n be a positive integer. Given a finite set A, a string of length n over A is an ordered n-tuple of elements of A written without parentheses or commas. The elements of A are called the characters of the string. The null string over A is defined to be the “string” with no characters. It is often denoted l and is said to have length 0. If A 5 {0, 1}, then a string over A is called a bit string.

So there's this statement and I'm just not sure what a string of length N over A is an ordered n-tuple of elements of A written without parentheses or commas. What exactly is a string of length N over a?? Am I just tired or what am I missing here this doesn't make sense to me and even later they say the null string over A what exactly does this mean?? A string over a set??

tommyd
  • 11
  • I guess they mean like a string of length n over A is like a set with one element which is just all the chars of the string? I'm not sure the over here is really confusing me. Like a string of length n over A just sounds weird to me what exactly is a string over a set? – tommyd Jan 17 '22 at 20:17

1 Answers1

3

An example of a string of length 10 over the english alphabet: helloworld. An example of a string of length 5 over the integers 0 through 9: 31337. An example of an ASCII string (mix of letters and digits and symbols) of length 8: tommyd#1. We can use other things other than these more common character sets as well. $\heartsuit\spadesuit\heartsuit\diamondsuit$ is a perfectly valid string of length 4 over the set of playing card suits and they give the example of strings specifically only using zeroes and/or ones being given the special name of "bit strings" such as 101101 or 000111 or even 11111. (note that 11111 is a perfectly valid example of a bit string even though no zeroes appeared. All that mattered was that every character that did appear was either a zero or a one)

Now... whether we wrote it as helloworld or if we wrote it as $(h,e,l,l,o,w,o,r,l,d)$ or as $\{(0,h),(1,e),(2,l),(3,l),(4,o),\dots\}$ or some other way, in maths we frequently switch between representations of these types of objects freely. All three of these are different ways of writing the string helloworld down. It can be useful to think of it as a function, it can be useful to think of it as a tuple, but it is shortest and easiest to write simply as the letters themselves without commas or parentheses etc... as it takes the least time and effort to write it that way.

As for the null string, also called the empty string, it is exactly as it sounds. It is the length zero string, the string with no characters appearing in it. If you think of the words appearing on a page in a book as a string, the empty string is simply the string corresponding to a blank page.

We can even begin listing the possible strings for a given set. The list of possible bit strings can start: , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, $\dots$. There are of course infinitely many overall, but there are $k^n$ strings of length $n$ using a character-set of size $k$.

JMoravitz
  • 79,518
  • +1 for taking the time to write this informative answer. I'd add only emphasize that thinking of strings of symbols from a set as words in an alphabet is (for me and maybe for the OP) the best summary. – Ethan Bolker Feb 05 '22 at 16:32