string
a string over an alphabet is a finite sequence of symbols from that alphabet.
[cite:@sipser_comp_2012]
we sometimes refer to a string by "word".
[cite:@sipser_comp_2012]
to concatenate a string with itself many times, we use the superscript notation 
to mean
[cite:@sipser_comp_2012]
to mean[cite:@sipser_comp_2012]the lexicographic order of strings is the same as the familiar dictionary order.
shortlex order or simply string order, is identical to lexicographic order, except that shorter strings precede longer strings. thus the string ordering of all strings over the alphabet
is 
.
[cite:@sipser_comp_2012]
shortlex order or simply string order, is identical to lexicographic order, except that shorter strings precede longer strings. thus the string ordering of all strings over the alphabet
is .[cite:@sipser_comp_2012]
we use the notation 
to denote the number of times the character 
occurs in a string 
.
to denote the number of times the character occurs in a string .let 
be words, then
be words, then