For example, if w = abbab, then {λ, a, ab, abb, abba, abbab} is the set of all
prefixes of w, while bab, ab, b are some of its suffixes.
Simple properties of strings, such as their length, are very intuitive and
probably need little elaboration. For example, if u and υ are strings, then the
length of their concatenation is the sum of the individual lengths, that is,
But although this relationship is obvious, it is useful to be able to make it
precise and prove it. The techniques for doing so are important in more
complicated situations.
Example 1.8
Show that (1.6) holds for any u and υ. To prove this, we first need a definition of
the length of a string. We make such a definition in a recursive fashion by
for all a ∈ ∑ and w any string on ∑. This definition is a formal statement of our
intuitive understanding of the length of a string: The length of a single symbol is
one, and the length of any string is increased by one if we add another symbol to
it. With this formal definition, we are ready to prove (1.6) by induction
characters.
By definition, (1.6) holds for all u of any length and all υ of length 1, so we
have a basis. As an inductive assumption, we take that (1.6) holds for all u of
any length and all υ of length 1, 2,…, n. Now take any υ of length n + 1 and
write it as υ = wa. Then,
By the inductive hypothesis (which is applicable since w is of length n),
so that