Strings

We’ll begin with a subject fundamental to both modeling computation and describing algorithms. Also, working with it properly provides an introduction to/reminder of the most important technique we’re going to be exploiting throughout the semester: induction/recursion. We’re going to discuss… strings!

Strings are the literal input to every formal model of computation we’ll work with in this class, so if you want to know the extent of what is possible with computation, we have to work with them. Also, strings (and more general sequences) are the input and output of nearly every problem we’ll solve when discussing algorithms. Formally, they’re how you specify these inputs and outputs.

From a more practical standpoint, all input and output on a physical computer along with the contents of their memory can be thought of as a string of bits or bytes. But to work with them and truly understand those things that use them, we’ll need formal definitions for what they are and how we can work with them. From a more theoretical standpoint, those definitions will use recursion, and in turn, nearly all proofs that we’re doing what we want with them will involve induction (which is really the same thing but translated to mathematician.) We’ll be leaning hard on recursion and induction throughout the semester, and strings will give us a great opportunity to start practicing.

For the rest of this lecture, though, I’m going to carefully define strings and some auxiliary things concerning them. Then, we’ll go through one or two proofs using these definitions and nothing else.

Now, you might believe you already know the definitions I’m about to give and think that the facts I’m about to prove are obvious. That’s fair. In fact, it’s kind of the point. I don’t want to surprise you with anything deep, but I do want you to see at the lowest level practical what is really going on. Doing so will force us to deal with how strings are recursive objects whose proofs require careful inductive arguments. And when we start working at a higher level of abstraction (which will be very soon if not during the next lecture,) we’ll have better intuition for what exactly we’re abstracting so we don’t cheat or get surprised by something.

Formal definition

Let \Sigma be an arbitrary finite set called an alphabet. The members of \Sigma are called characters or symbols. I’ll try to stick to symbol in class and in these notes.

For example, we might have \Sigma = \{\text{A}, \text{B}, \dots, \text{Z}\}, but typically—especially when discussing models of computation—\Sigma = \{0, 1\}. A string (sometimes called a word (which is not to be confused with 16 32 64-bit units of memory)) over \Sigma is a finite sequence of zero or more symbols from \Sigma.

Unfortunately, what I’ve written so far is still a bit more informal than we’d like for now, because it doesn’t reveal the recursive structure of strings (or other sequences.) Formally a string w over \Sigma is defined recursively as one of the following:

• the empty string, denoted by the Greek letter \varepsilon (epsilon)
• or an ordered pair (a, x) where a is some symbol of \Sigma and x is a string over \Sigma

So, while we might normally write a string like STRING by just smashing the symbols together in order, the string we’re really working with is (\text{S}, \text{TRING}) = (\text{S}, (\text{T}, \text{RING})) = \dots = (\text{S}, (\text{T}, (\text{R}, (\text{I}, (\text{N}, (\text{G}, \varepsilon)))))). That’s a pain to write, though (I probably have poorly paired parentheses even in this one example), so I’ll stick to the common form when possible. And even when going just “one layer deep”, I’ll almost certainly write a \cdot x (with a little dot) or ax instead of (a, x).

Function definitions

Strings are formally defined recursively, so formal definitions of basic functions have to be recursive as well, and they need to be based on the same recursive structure as the strings themselves. As an example, the informal definition of the length |w| of a string w is the number of symbols in w. But for a formal definition, we need a more systematic way to describe counting symbols.

Formally, the length |w| of a string w is defined as follows: |w| := \begin{cases} 0 & \text{if $w = \varepsilon$}\\ 1 + |x| & \text{if $w = ax$} \end{cases} For example \begin{aligned} |\text{HAT}| &= 1 + |\text{AT}|\\ &= 1 + (1 + |\text{T}|)\\ &= 1 + (1 + (1 + |\varepsilon|))\\ &= 1 + (1 + (1 + 0))\\ &= 3. \end{aligned}

Informally, the concatenation of two strings w and z, denoted w \bullet z or wz is the unique string with the symbols of w in order followed by the symbols of z in order. (You might observe that I’m using a thicker dot for concatenation of two strings than I was for the syntactic sugar of building a string.) Defining the concatenation w \bullet z recursively is far less obvious than defining length, in my opinion.

So how might we do so? Well, the output of our function needs to be a string, so it might help to remember what a string consists of. Generally, it begins with a single starting symbol, and generally, this symbol should match the first symbol of w, and it should be followed by everything else in the output string. Specifically, when w = a \cdot x for some symbol a, the everything else would be all of x followed by all of z. Oh, the everything else is, by (informal) definition, the concatenation of x and z. The only time the above reasoning doesn’t work is when w itself is empty, but it stands to reason (and we can make it part of the definition) that nothing followed by any something z is just z itself.

So, formally, the concatenation w \bullet z of strings w and z (also denoted wz) is defined as follows: w \bullet z := \begin{cases} z & \text{if $w = \varepsilon$}\\ a \cdot (x \bullet z) & \text{if $w = ax$} \end{cases} For example \begin{aligned} \text{NOW} \bullet \text{HERE} &= \text{N} \cdot (\text{OW} \bullet \text{HERE})\\ &= \text{N} \cdot (\text{O} \cdot (\text{W} \bullet \text{HERE}))\\ &= \text{N} \cdot (\text{O} \cdot (\text{W} \cdot (\varepsilon \bullet \text{HERE})))\\ &= \text{N} \cdot(\text{O} \cdot (\text{W} \cdot \text{HERE})))\\ &= \text{NOWHERE}. \end{aligned}

Induction

The formal definition of strings is recursive. The formal definition of basic functions over string is also recursive. It seems natural, then, to do prove things about them recursively inductively.

In principle, there’s a few ways of writing and thinking about inductive proofs, but we highly recommend and will enforce via our standard rubric (at least when asking for low-level proofs about strings) the following approach. In short, you should write a direct proof that

1. begins by considering an arbitrary object (it’s the proof of a universally quantified statement, after all) of some arbitrary specified size (probably n),
2. explicitly states a strong induction hypothesis based on objects of some strictly smaller size (probably k < n),
3. explicitly handles each case for the arbitrary starting object (with cases typically mirroring that of the recursive definitions),
4. nonchalantly using the induction hypothesis when convenient (it’s just like any other assumption statement), and
5. ends by pointing out that all the cases came to the desired conclusion

Again, your proof should use a strong induction hypothesis (which is always just as good or better than weak), and your proof should consider an arbitrary object of some size n and reduce to an induction hypothesis concerning objects of size k < n. As we get through the semester, and especially when we start discussing recursive algorithms, you’ll find it increasingly difficult not to do both of those things. So, you should start practicing now!

For basic facts about strings, you’d typically use the following template. Hell, you’ll probably want to copy-paste it. Suppose we wanted to prove that every string is perfectly cromulant¹, whatever that means. The recursive definition of strings has two cases, so our proof will probably have two cases, as well.

We feel so strongly that the above is the “correct” way to write—and think about!—induction that we will take points off of homework and exam proofs that use a weak induction hypothesis (only considers strings of length one less) or (God forbid) attempt to “build up” arbitrary objects from ones you assume the statement is true for. It’s incredibly easy to mess up these latter types of proofs.

Examples

Let’s prove a few “obvious” lemmas using the above template.

Lemma (adding nothing does nothing): For every string w, we have w \bullet \varepsilon = w.

Again, I know this statement is “obvious”. In fact, it almost appears to be a restatement of the definition of concatenation. However, the definition had the \varepsilon on the left! We need to actually verify that putting it on the right works how we would expect.

The next example is a bit more complicated.

Lemma (the length of a concatenation is the sum of lengths): |w \bullet z| = |w| + |z| for all strings w and z.

This one is trickier, because there are two strings and it’s not immediately clear what we should be doing induction on. However, it also gives me an opportunity to explain how I like to come up with these proofs. Despite how these proofs are usually written, we should start by ignoring the base cases. We haven’t even decided what to do induction over, so how can we know what the base cases are going to be?

So for now, suppose both w and z are “long enough” that we’re unlikely to be in a base case. In this case, we observe |w \bullet z| = |(a \cdot x) \bullet z| for some symbol a and string x, because w is long and the definition of concatenation is based on breaking up w in this way. So then |w \bullet z| = |a \cdot (x \bullet z)| = 1 + |x \bullet z| by the definitions of both concatenation and length. Oh, and now we’re trying to evaluate the length of a concatenation where the string on the left (here given as x) is shorter than when we started, and we can apply the induction hypothesis on that shorter string. With a little bit more grinding (which you’ll see in a minute), we can easily verify that it works out. In particular, the only situation where we can’t break up w like that is if w = \varepsilon, but that situation ends up being an easily handled base case.

One final trick that won’t be obvious just from looking at the proof below: When going through a relatively long line of equalities like we’ll be doing for the general (inductive) case, it’s often helpful to write the starting point (in the upper left) along with the target (at the bottom right) and work both directions toward some common middle (probably around where the induction hypothesis should be used.)³

There are more proof examples and useful string definitions in Erickson’s typeset lecture notes. You should read these. In addition, the lab following this lecture will give you guided practice on writing inductive proofs over strings. You should attend as many labs as you can for the practice. Similar difficulty problems will appear on exams.

Let’s try one more proof.

Lemma (concatenation is associative): (w \bullet y) \bullet z = w \bullet (y \bullet z) for all strings w, y, and z.

Like in the second example, we’re working with multiple strings, and like in the first example, we’re working directly with a string as the “type” of each side of the equality. And, in general, the definition of concatenation suggests the first symbol of each string has to be the first symbol of w. Let’s do induction on w (and only w,) again.

In the next lecture, we’ll start discussing models of computation in earnest with the typical goal of describing infinite sets of strings using finite descriptions.