We start with a finite, nonempty set ∑ of symbols, called the alphabet. From
the individual symbols we construct strings, which are finite sequences of
symbols from the alphabet. For example, if the alphabet ∑ = {a, b}, then abab
and aaabbba are strings on ∑. With few exceptions, we will use lowercase
letters a, b, c,…for elements of ∑ and u, υ, ω,…for string names. We will write,
for example,
to indicate that the string named w has the specific value abaaa.
The concatenation of two strings w and υ is the string obtained by
appending the symbols of υ to the right end of w, that is, if
and
then the concatenation of w and υ, denoted by wυ, is
The reverse of a string is obtained by writing the symbols in reverse order; if w
is a string as shown above, then its reverse w R is
The length of a string w, denoted by |w|, is the number of symbols in the
string. We will frequently need to refer to the empty string, which is a string
with no symbols at all. It will be denoted by λ. The following simple relations
hold for all w.
Any string of consecutive symbols in some w is said to be a substring of w.
If
then the substrings υ and u are said to be a prefix and a suffix of w, respectively.