Models of Computation

Lecture 1: Strings [Sp’18]

Vario, inquit [Epicurus], ordine ac positione conveniunt atomi sicut literae, quae cum sint paucae,
varie tamen collocatae innumerabilia verba conficiunt.
[Atoms, like letters, says Epicurus, come together in various orders and positions; there are few ofthem, but different combinations produce countless words.]— Gottfried Leibniz, Dissertatio de Arte Combinatoria (1666)
THOMAS GODFREY, a self-taught mathematician, great in his way, and afterward inventor of what isnow called Hadley’s Quadrant. But he knew little out of his way, and was not a pleasing companion;as, like most great mathematicians I have met with, he expected universal precision in everythingsaid, or was forever denying or distinguishing upon trifles, to the disturbance of all conversation.
He soon left us.
— Benjamin Franklin, Memoirs, Part 1 (1771)
describing one of the founding members of the Junto
If indeed, as Hilbert asserted, mathematics is a meaningless game played with meaningless marks
on paper, the only mathematical experience to which we can refer is the making of marks on paper.
— Eric Temple Bell, The Queen of the Sciences (1931)

1

Strings

Throughout this course, we will discuss dozens of algorithms and computational models thatmanipulate sequences: one-dimensional arrays, linked lists, blocks of text, walks in graphs,
sequences of executed instructions, and so on. Ultimately the input and output of any algorithm
must be representable as a finite string of symbols—the raw contents of some contiguous portionof the computer’s memory. Reasoning about computation requires reasoning about strings.
This note lists several formal definitions and formal induction proofs related to strings. These
definitions and proofs are intentionally much more detailed than normally used in practice—mostpeople’s intuition about strings is fairly accurate—but the extra precision is necessary for any
sort of formal proof. It may be helpful to think of this material as part of the “assembly language”
of theoretical computer science. We normally think about computation at a much higher levelof abstraction, but ultimately every argument must “compile” down to these (and similar)
definitions.
But the actual definitions and theorems are not the point. The point of playing with thismaterial is to get some experience working with formal/mechanical definitions and proofs,
especially inductive definitions and recursive proofs. Or should I say recursive definitions andinductive proofs? Whatever,they’re the same thing. Strings are a particularly simple andinduct
convenient playground for recurs ion; we’ll see many more examples throughout the course.
When you read this note, don’t just look at the content of the definitions and proofs; pay close
attention to their structure and the process for creating them.

1.1

Strings

Fix an arbitrary finite set Σ called the alphabet; the individual elements of Σ are called symbols
or characters. As a notational convention, I will always use lower-case letters near the start of
the English alphabet (a, b, c, . . . ) as symbol variables, and never as explicit symbols. For explicit
symbols, I will always use fixed-width upper-case letters (A, B, C, . . . ), digits (0, 1, 2, . . . ),© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

1Models of Computation

Lecture 1: Strings [Sp’18]

or other symbols (, $, #, •, . . . ) that are clearly distinguishable from variables. For further
emphasis, I will almost always typeset explicit symbols in RED.
A string (or word) over Σ is a finite sequence of zero or more symbols from Σ. Formally, astring w over Σ is defined recursively as either• the empty string, denoted by the Greek letter " (epsilon), or• an ordered pair (a, x ), where a is a symbol in Σ and x is a string over Σ.
We normally write either a · x or simply ax to denote the ordered pair (a, x). Similarly, we
normally write explicit strings as sequences of symbols instead of nested ordered pairs; forexample, STRING is convenient shorthand for the formal expression (S, (T, (R, (I, (N, (G, ")))))).
As a notational convention, I will always use lower-case letters near the end of the English
alphabet (. . . , w, x, y, z) for string variables, and SHOUTY  RED  MONOSPACED  TEXT to typeset
explicit (non-empty) strings.
The set of all strings over Σ is denoted Σ∗ (pronounced “sigma star”). It is very important toremember that every element of Σ∗ is a finite string, although Σ∗ itself is an infinite set containing
strings of every possible finite length.

1.2

Two Recursive Functions

Our first several proofs about strings will involve two natural functions, one giving the length ofa string, the other gluing two strings together into a larger string. These two function behave
exactly the way you think they do, but if we actually want to prove anything about them, we firsthave to define them in a way that supports formal proofs. Because the objects on which thesefunctions act—strings–are defined recursively, the functions must also be defined recursively.
The length |w | of a string w is the number of symbols in w, defined formally as follows:¨
0
if w = ",|w| :=
1 + |x| if w = a x.
For example, the string FIFTEEN has length 7, the string SEVEN has length 5, and the string 5
has length 1. Although they are formally different objects, we do not normally distinguishbetween symbols and strings of length 1.
The concatenation of two strings x and y, denoted either x • y or simply x y, is theunique string containing the characters of x in order, followed by the characters in y inorder. For example, the string NOWHERE is the concatenation of the strings NOW and HERE;
that is, NOW • HERE = NOWHERE. (On the other hand, HERE • NOW = HERENOW.) Formally,
concatenation is defined recusively as follows:¨z
if w = ",w • z :=a · (x • z) if w = a x.
(Here I’m using a larger dot • to formally distinguish the operator that concatenates two arbitrary
strings from from the syntactic sugar · that builds a string from a single character and a string.)
When we describe the concatenation of more than two strings, we normally omit all dots
and parentheses, writing wxyz instead of (w • (x • y)) • z, for example. This simplification isjustified by the fact (which we will prove shortly) that the function • is associative.

2

Models of Computation

1.3

Lecture 1: Strings [Sp’18]

Induction on Strings

Induction is the standard technique for proving statements about recursively defined objects.
Hopefully you are already comfortable proving statements about natural numbers via induction,
but induction is actually a far more general technique. Several different variants of induction
can be used to prove statements about more general structures; here I describe the variant
that I recommend (and actually use in practice). This variant follows two primary design
considerations:• The case structure of the proof should mirror the case structure of the recursive definition. For example, if you are proving something about all strings, your proof should have
two cases: Either w = ", or w = a x for some symbol a and string x.
• The inductive hypothesis should be as strong as possible. The (strong) inductive hypothesis for statements about natural numbers is always “Assume there is no counterexample ksuch that k < n.” I recommend adopting a similar inductive hypothesis for strings: “Assume
there is no counterexample x such that |x| < |w|.” Then for the case w = a x, we have|x| = |w| − 1 < |w| by definition of |w|, so the inductive hypothesis applies to x.
Thus, string-induction proofs have the following boilerplate structure. Suppose we want to provethat every string is perfectly cromulent, whatever that means. The white boxes hide additional
proof details that, among other things, depend on the precise definition of “perfectly cromulent”.
Proof: Let w be an arbitrary string.
Assume, for every string x such that |x| < |w|, that x is perfectly cromulent.
There are two cases to consider.

• Suppose w = " .

Therefore, w is perfectly cromulent.

• Suppose w = a x for some symbol a and string x .
The induction hypothesis implies that x is perfectly cromulent.

Therefore, w is perfectly cromulent.
In both cases, we conclude that w is perfectly cromulent.



Here are three canonical examples of this proof structure. When developing proofs in thisstyle, I strongly recommend first mindlessly writing the green text (the boilerplate) with lots ofspace for each case, then filling in the red text (the actual theorem and the induction hypothesis),and only then starting to actually think.
Many students are confused (or at least bored and distracted) by the fact that we are proving
mind-bogglingly obvious facts. If you’re one of these students, try to remember that the lemmas
themselves are not the point. Pay close attention to the structure of the proofs. Notice how each
proof follows the boilerplate described above. Notice how every sentence of the proof follows
mechanically from earlier sentences, definitions, and the rules of standard logic and arithmetic.
Lemma 1.1. Adding nothing does nothing: For every string w, we have w • " = w.
3

Models of Computation

Lecture 1: Strings [Sp’18]

Proof: Let w be an arbitrary string. Assume that x • " = x for every string x such that |x| < |w|.
There are two cases to consider:• Suppose w = ".
w•" ="•"

because w = ",="by definition of concatenation,=w

because w = ".

• Suppose w = a x for some symbol a and string x.
w • " = (a · x) • "because w = a x,

= a · (x • ")by definition of concatenation,=a·x

by the inductive hypothesis,=w

because w = a x.

In both cases, we conclude that w • " = w.



Lemma 1.2. Concatenation adds length: |w • x| = |w| + |x| for all strings w and x.
Proof: Let w and x be arbitrary strings. Assume that | y • x| = | y| + |x| for every string y suchthat | y| < |w|. (Notice that we are using induction only on w, not on x.) There are two cases toconsider:• Suppose w = ".
|w • x| = |" • x|

because w = "= |x|

by definition of •= |"| + |x||"| = 0 by definition of | · |= |w| + |x|

because w = "• Suppose w = a y for some symbol a and string y.
|w • x| = |a y • x|

because w = a y= |a · ( y • x)|

by definition of •= 1 + | y • x|

by definition of | · |= 1 + | y| + |x|

by the inductive hypothesis= |a y| + |x|

by definition of | · |= |w| + |x|

because w = a y

In both cases, we conclude that |w • x| = |w| + |x|.

Lemma 1.3. Concatenation is associative: (w • x) • y = w • (x • y) for all strings w, x, and y.
Proof: Let w, x, and y be arbitrary strings. Assume that (z • x) • y = z • (x • y) for every stringz such that |z| < |w|. (Again, we are using induction only on w.) There are two cases to consider.
4Models of Computation

Lecture 1: Strings [Sp’18]• Suppose w = ".
(w • x) • y = (" • x) • ybecause w = "=x•yby definition of •= " • (x • y)by definition of •= w • (x • y)because w = "• Suppose w = az for some symbol a and some string z.
(w • x) • y = (az • x) • ybecause w = az

= (a · (z • x)) • y

by definition of •= a · ((z • x) • y)by definition of •= a · (z • (x • y))by the inductive hypothesis= az • (x • y)by definition of •= w • (x • y)because w = az

In both cases, we conclude that (w • x) • y = w • (x • y).

1.4

More Than One Path up the Mountain

This is not the only boilerplate that one can use for induction proofs on strings. For example,
we can model our case analysis on the following observation, whose easy proof we leave as an
exercise (hint, hint): A string w ∈ Σ∗ is non-empty if and only if either• w = a for some symbol a ∈ Σ, or• w = x • y for some non-empty strings x and y.
In the latter case, Lemma 1.2 implies that |x| < |w| and | y| < |w|, so in an inductive proof, we
can apply the inductive hypothesis to either x or y (or even both).
Here is a proof of Lemma 1.3 that uses this alternative recursive structure:
Proof: Let w, x, and y be arbitrary strings. Assume that (z • x 0 ) • y 0 = z • (x 0 • y 0 ) for all strings
x 0 , y 0 , and z such that |z| < |w|. (We need a stronger induction hypothesis here than in theprevious proofs!) There are three cases to consider.
• Suppose w = ".
(w • x) • y = (" • x) • ybecause w = "=x•yby definition of •= " • (x • y)by definition of •= w • (x • y)because w = "• Suppose w is equal to some symbol a.
(w • x) • y = (a • x) • ybecause w = a= (a · x) • ybecause a • z = a · z by definition of •= a · (x • y)by definition of •= a • (x • y)because a • z = a · z by definition of •= w • (x • y)because w = a5Models of Computation

Lecture 1: Strings [Sp’18]• Suppose w = u • v for some nonempty strings u and v.
(w • x) • y = ((u • v) • x) • ybecause w = u • v= (u • (v • x)) • yby the inductive hypothesis, because |u| < |w|= u • ((v • x) • y)by the inductive hypothesis, because |u| < |w|= u • (v • (x • y))by the inductive hypothesis, because |v| < |w|= (u • v) • (x • y)by the inductive hypothesis, because |u| < |w|= w • (x • y)because w = u • v

In all three cases, we conclude that (w • x) • y = w • (x • y).

1.5Indices, Substrings, and Subsequences

Finally, I’ll conclude this note by formally defining several other common functions and terms
related to strings.
For any string w and any integer 1 ≤ i ≤ |w|, the expression wi denotes the ith symbol in w,
counting from left to right. More formally, w i is recursively defined as follows:¨aif w = a x and i = 1,
w i :=
x i−1 if w = a x and i > 1.
As one might reasonably expect, w i is formally undefined if i < 1 or w = ", and therefore (byinduction) if i > |w|. The integer i is called the index of w i .
We sometimes write strings as a concatenation of their constituent symbols using this subscript
notation: w = w1 w2 · · · w|w| . While completely standard, this notation is slightly misleading,because it incorrectly suggests that the string w contains at least three symbols, when in fact w
could be a single symbol or even the empty string.
In actual code, subscripts are usually expressed using the bracket notation w [i]. Brackets
were introduced as a typographical convention over a hundred years ago because subscripts andsuperscripts1 were difficult or impossible to type.2 We sometimes write strings as explicit arraysw[1 .. n], with the understanding that n = |w|. Again, this notation is potentially misleading;always remember that n might be zero; the string/array could be empty.
A substring of a string w is another string obtained from w by deleting zero or more symbols
from the beginning and from the end. Formally, a string y is a substring of w if and only ifthere are strings x and z such that w = x yz. Extending the array notation for strings, we write
w [i .. j ] to denote the substring of w starting at w i and ending at w j . More formally, we define¨"
if j < i,w[i .. j] :=w i · w[i + 1 .. j] otherwise.
1The same bracket notation is also used for bibliographic references, instead of the traditional footnote/endnote
superscripts, for exactly the same reasons.
2A typewriter is an obsolete mechanical device loosely resembling a computer keyboard. Pressing a key on a
typewriter moves a lever (called a “typebar”) that strikes a cloth ribbon full of ink against a piece of paper, leaving theimage of a single character. Many historians believe that the ordering of letters on modern keyboards (QWERTYUIOP)
evolved in the late 1800s, reaching its modern form on the 1874 Sholes & Glidden Type-WriterTM , in part to separate
many common letter pairs, to prevent typebars from jamming against each other; this is also why the keys on mostmodern keyboards are arranged in a slanted grid. (The common folk theory that the ordering was deliberately
intended to slow down typists doesn’t withstand careful scrutiny.) A more recent theory suggests that the ordering
was influenced by telegraph3 operators, who found older alphabetic arrangements confusing, in part because of
ambiguities in American Morse Code.

6

Models of Computation

Lecture 1: Strings [Sp’18]

A proper substring of w is any substring other than w itself. For example, LAUGH is a proper
substring of SLAUGHTER. Whenever y is a (proper) substring of w, we also call w a (proper)
superstring of y.
A prefix of w[1 .. n] is any substring of the form w[1 .. j]. Equivalently, a string p is a prefixof another string w if and only if there is a string x such that p x = w. A proper prefix of w isany prefix except w itself. For example, DIE is a proper prefix of DIET.
Similarly, a suffix of w[1 .. n] is any substring of the form w[i .. n]. Equivalently, a string s is asuffix of a string w if and only if there is a string x such that xs = w. A proper suffix of w is
any suffix except w itself. For example, YES is a proper suffix of EYES, and HE is both a proper
prefix and a proper suffix of HEADACHE.
A subsequence of a string w is a string obtained by deleting zero or more symbols fromanywhere in w. More formally, z is a subsequence of w if and only if• z = ", or• w = a x for some symbol a and some string x such that z is a subsequence of x.
• w = a x and z = a y for some symbol a and some strings x and y, and y is a subsequenceof x.
A proper subsequence of w is any subsequence of w other than w itself. Whenever z is a (proper)
subsequence of w, we also call w a (proper) supersequence of z.
Substrings and subsequences are not the same objects; don’t confuse them! Every substringof w is also a subsequence of w, but not every subsequence is a substring. For example, METAL isa subsequence, but not a substring, of MEATBALL. To emphasize the distinction, we sometimes
redundantly refer to substrings of w as contiguous substrings, meaning all their symbols appear
together in w.

Exercises
Most of the following exercises ask for proofs of various claims about strings. Here “prove” means
give a complete, self-contained, formal proof by inductive definition-chasing, using the boilerplate
structure recommended in Section 1.3. Feel free to use Lemmas 1.1, 1.2, and 1.3 without proof,
but don’t assume any other facts about strings that you have not actually proved. (Some later
exercises rely on results proved in earlier exercises.) Do not appeal to intuition, and do not use
the words “obvious” or “clearly” or “just”. Most of these claims are in fact obvious; the real
exercise is understanding and formally expressing why they’re obvious.

3A telegraph is an obsolete electromechanical communication device consisting of an electrical circuit with aswitch at one end and an electromagnet at the other. The sending operator would press and release a key, closing andopening the circuit, originally causing the electromagnet to push a stylus onto a moving paper tape, leaving marksthat could be decoded by the receiving operator. (Operators quickly discovered that they could directly decode theclicking sounds made by the electromagnet, and so the paper tape became obsolete almost immediately.) The mostcommon scheme within the US to encode symbols, developed by Alfred Vail and Samuel Morse in 1837, used (mostly)
short (·) and long (−) marks—now called “dots” and “dashes”, or “dits” and “dahs”—separated by gaps of various
lengths. American Morse code (as it became known) was ambiguous; for example, the letter Z and the string SE wereboth encoded by the sequence · · · · (“di-di-dit, dit”). This ambiguity has been blamed for the S key’s position on thetypewriter keyboard near E and Z.
Vail and Morse were of course not the first people to propose encoding symbols as strings of bits. That honor
apparently falls to Francis Bacon, who devised a five-bit binary encoding of the alphabet (except for the letters J and U)
in 1605 as the basis for a steganographic code—a method or hiding secret message in otherwise normal text.

7Models of Computation

Lecture 1: Strings [Sp’18]

Note to instructors: Do not assign any of these problems before solving themyourself, especially on exams. It’s very easy to underestimate the difficulty of these
problems, or at least the lengths of their solutions, which for exams is a reasonable proxyfor difficulty. Also, several later exercises rely implicitly on identities like #(a, x • y) =#(a, x) + #(a, y) that are only proved in earlier exercises. It’s unfair to assign these problems
to students without telling them which earlier results they can use.

Useful Facts About Strings
1. Let w be an arbitrary string, and let n = |w|. Prove each of the following statements.
(a) w has exactly n + 1 prefixes.
(b) w has exactly n proper suffixes.
(c) w has at most n(n + 1)/2 distinct substrings. (Why “at most”?)(d) w has at most 2n − 1 distinct proper subsequences. (Why “at most”?)

2. Prove the following useful identities for all strings w, x, y, and z directly from the definitionof •, without referring to the length of any string.
(a) If x • y = x, then y = ".
(b) If x • y = y, then x = ".
(c) If x • z = y • z, then x = y.
(d) If x • y = x • z, then y = z.

3. Prove the following useful fact about substrings. An arbitrary string x is a substring ofanother arbitrary string w = u • v if and only if at least one of the following conditions
holds:• x is a substring of u.
• x is a substring of v.
• x = yz where y is a suffix of u and z is a prefix of v.

4. Let w be an arbitrary string, and let n = |w|. Prove the following statements for all indices1 ≤ i ≤ j ≤ k ≤ n.
(a) |w[i .. j]| = j − i + 1(b) w[i .. j] • w[ j + 1 .. k] = w[i .. k](c) wR [i .. j] = (w[i 0 .. j 0 ])R where i 0 + j = j 0 + i = |w| + 1.
Recursive Functions
5. For any symbol a and any string w, let #(a, w ) denote the number of occurrences of ain w. For example, #(A, BANANA) = 3 and #(X, FLIBBERTIGIBBET) = 0.
(a) Give a formal recursive definition of the function #: Σ × Σ∗ → N.
8

Models of Computation

Lecture 1: Strings [Sp’18](b) Prove that #(a, x y) = #(a, x) + #(a, y) for every symbol a and all strings x and y.
Your proof must rely on both your answer to part (a) and the formal recursive
definition of string concatenation.
(c) Prove the following identity for all alphabets Σ and all strings w ∈ Σ∗ :X
|w| =#(a, w)a∈Σ[Hint: Don’t try to use induction on Σ.]

6. The reversal w R of a string w is defined recursively as follows:("
if w = "wR :=x R • a if w = a · x(a) Prove that (wR )R = w for every string w.
(b) Prove that |wR | = |w| for every string w.
(c) Prove that (w • x)R = x R • wR for all strings w and x.
(d) Prove that #(a, wR ) = #(a, w) for every string w and every symbol a. (See Exercise 5.)

7. For any string w and any non-negative integer n, let w n denote the string obtained byconcatenating n copies of w; more formally, we define("
if n = 0
wn :=
n−1
w•w
otherwise
For example, (BLAH)5 = BLAHBLAHBLAHBLAHBLAH and " 374 = ".
(a) Prove that wm • wn = wm+n for every string w and all non-negative integers n and m.
(b) Prove that #(a, wn ) = n · #(a, w) for every string w, every symbol a, and every
non-negative integer n. (See Exercise 5.)(c) Prove that (wR )n = (wn )R for every string w and every non-negative integer n.
(d) Prove that for all strings x and y that if x • y = y • x, then x = wm and y = wn forsome string w and some non-negative integers m and n. [Hint: Careful with "!]8. The complement w c of a string w ∈ {0, 1}∗ is obtained from w by replacing every 0 in w
with a 1 and vice versa. The complement function can be defined recursively as follows:
if w = ""ccw := 1 · x if w = 0 x
0 · x c if w = 1 x(a) Prove that |w| = |wc | for every string w.
9Models of Computation

Lecture 1: Strings [Sp’18](b) Prove that (x • y)c = x c • y c for all strings x and y.
(c) Prove that #(1, w) = #(0, wc ) for every string w.
(d) Prove that (wR )c = (wc )R for every string w.
(e) Prove that (wn )c = (wc )n for every string w and every non-negative integer n.
9. For any string w ∈ {0, 1, 2}∗ , let w + denote the string obtained from w by replacing eachsymbol a in w by the symbol corresponding to (a + 1) mod 3. for example, 0102101+ =1210212. This function can be defined more formally as follows:
"
if w = "



+
1· x
if w = 0 x
w+ :=
+

2· x
if w = 1 x



+
0· x
if w = 2 x(a) Prove that |w| = |w+ | for every string w ∈ {0, 1, 2}∗ .
(b) Prove that (x • y)+ = x + • y + for all strings x, y ∈ {0, 1, 2}∗ .
(c) Prove that #(1, w+ ) = #(0, w) for every string w ∈ {0, 1, 2}∗ .
(d) Prove that (w+ )R = (wR )+ for every string w ∈ {0, 1, 2}∗ .
10. For any string w ∈ {0, 1}∗ , let swap(w) denote the string obtained from w by swapping thefirst and second symbols, the third and fourth symbols, and so on. For example:
swap(101) = 011
swap(100111) = 011011
swap(10 11 00 01 10 1) = 01 11 00 10 01 1.
The swap function can be formally defined as follows:
if w = ""swap(w) := w
if w = 0 or w = 1
 ba • swap(x) if w = a b x for some a, b ∈ {0, 1} and x ∈ {0, 1}∗(a) Prove that |swap(w)| = |w| for every string w.
(b) Prove that swap(swap(w)) = w for every string w.
(c) Prove that swap(wR ) = (swap(w))R for every string w such that |w| is even. [Hint: Your
proof must invoke four different recursive definitions: reversal wR , concatenation •,length |w|, and the swap function!]
11. For any string w ∈ {0, 1}∗ , let sort(w) denote the string obtained by sorting the charactersin w. For example, sort(010101) = 000111. The sort function can be defined recursively
as follows:
if w = ""sort(w) :=0 · sort(x) if w = 0 x
sort(x) • 1 if w = 1 x

Prove the following for all strings w, x, y ∈ {0, 1}∗ :10Models of Computation

Lecture 1: Strings [Sp’18](a) Prove that sort(w) ∈ 0∗ 1∗ for every string w ∈ {0, 1}∗ .
(b) Prove that #(0, w) = #(0, sort(w)) for every string w ∈ {0, 1}∗ .
(c) Prove that |w| = |sort(w)|, for every string w ∈ {0, 1}∗ .
(d) Prove that sort(w) = 0#(0,w) 1#(1,w) , for every string w ∈ {0, 1}∗ . (In other words,
prove that our recursive definition is correct.)(e) Prove that sort(wR ) = sort(w), for every string w ∈ {0, 1}∗ .
12. Consider the following recursively defined function:
y
if x = "if y = "xmerge(x, y) := 0 · merge(w, y) if x = 0w


0 · merge(x, z) if y = 0z
1 · merge(w, y) if x = 1w and y = 1z
For example:
merge(10, 10) = 1010
merge(10, 010) = 01010
merge(010, 0001100) = 0000101100(a) Prove that merge(x, y) ∈ 0∗ 1∗ for all strings x, y ∈ 0∗ 1∗ . (The regular expression0∗ 1∗ is shorthand for the language {0a 1 b | a, b ≥ 0}.)(b) Prove that sort(x • y) = merge(sort(x), sort( y)) for all strings x, y ∈ {0, 1}∗ . (Thesort function is defined in the previous exercise.)
13. Consider the following pair of mutually recursive functions on strings:(("
if w = ""if w = "evens(w) :=odds(w) :=odds(x) if w = a x
a · evens(x) if w = a x
For example, evens(MISSISSIPPI) = ISSIP and odds(MISSISSIPPI) = MSISPI.
(a) Prove the following identity for all strings w and x:(
evens(w) • evens(x) if |w| is even,evens(w • x) =evens(w) • odds(x) if |w| is odd.
(b) State and prove a similar identity for odds(w • x).
(c) Prove that every string w is a shuffle of evens(w) and odds(w).
14. Consider the following recursively defined function:¨"
if w = "stutter(w) :=aa • stutter(x) if w = a x
For example, stutter(MISSISSIPPI) = MMIISSSSIISSSSIIPPPPII.
11

Models of Computation

Lecture 1: Strings [Sp’18](a) Prove that |stutter(w)| = 2|w| for every string w.
(b) Prove that evens(stutter(w)) = w for every string w.
(c) Prove that odds(stutter(w)) = w for every string w.
(d) Prove that stutter(w) is a shuffle of w and w, for every string w.
(e) Prove that w is a palindrome if and only if stutter(w) is a palindrome, for every
string w.

15. Consider the following recursive function:¨
z
if w = "faro(w, z) :=a · faro(z, x) if w = a x
For example, faro(0011, 0101) = 00011011. (A "faro shuffle" splits a deck of cards into
two equal piles and then perfectly interleaves them.)(a) Prove that |faro(x, y)| = |x| + | y| for all strings x and y.
(b) Prove that faro(w, w) = stutter(w) for every string w.
(c) Prove that faro(odds(w), evens(w)) = w for every string w.

16. For any string w, let declutter(w) denote the string obtained from w by deleting any symbolthat equals its immediate successor. For example, declutter(MISSISSIPPI) = MISISIPI,
and declutter(ABBCCCAAAACCCBBA) = ABCACBA.
(a) Given a recursive definition for the function declutter.
(b) Using your recursive definition, prove that declutter(stutter(w)) = declutter(w) for
every string w.
(c) Using your recursive definition, prove that declutter(wR ) = (declutter(w))R for every
string w.
(d) Using your recursive definition, prove that w is a palindrome if and only if declutter(w)is a palindrome, for every string w.

17. Consider the following recursively defined function¨"
if w = "hanoi(w) =hanoi(x) • a • hanoi(x) if w = a x
Prove that |hanoi(w)| = 2|w| − 1 for every string w.

18. Consider the following recursively defined function¨"
if w = "slog(w) =a · slog(evens(w)) if w = a xProve that |slog(w)| = log2 (|w| + 1) for every string w.
12Models of Computation

Lecture 1: Strings [Sp’18]

19. Consider the following recursively defined function¨
w
if |w| ≤ 1
bitrev(w) =bitrev(odds(w)) • bitrev(evens(w)) otherwise(a) Prove that |bitrev(w)| = |w| for every string w.
? (b)Prove that bitrev(bitrev(w)) = w for every string w such that |w| is a power of 2.

20. The binary value of any string w ∈ {0, 1}∗ is the integer whose binary representation(possibly with leading 0s) is w. The value function can be defined recursively as follows:
if w = "0value(w) := 2 · value(x)if w = x • 02 · value(x) + 1 if w = x • 1(a) Prove that value(w) + value(wc ) = 2|w| − 1 for every string w ∈ {0, 1}∗ .
(b) Prove that value(x • y) = value(x) · 2| y| + value( y) for all strings x, y ∈ {0, 1}∗ .
? (c)Prove that value(x) is divisible by 3 if and only if value(x R ) is divisible by 3.

Recursively Defined Sets
20. Recursively define a set L of strings over the alphabet {0, 1} as follows:• The empty string " is in L.
• For any two strings x and y in L, the string 0 x 1 y 0 is also in L.
• These are the only strings in L.
(a) Prove that the string 000010101010010100 is in L.
(b) Prove by induction that every string in L has exactly twice as many 0s as 1s. (You may
assume the identity #(a, x y) = #(a, x) + #(a, y) for any symbol a and any strings x
and y; see Exercise 5(b).)(c) Give an example of a string with exactly twice as many 0s as 1s that is not in L.

21. Recursively define a set L of strings over the alphabet {0, 1} as follows:• The empty string " is in L.
• For any two strings x and y in L, the string 0 x 1 y is also in L.
• For any two strings x and y in L, the string 1 x 0 y is also in L.
• These are the only strings in L.
(a) Prove that the string 01000110111001 is in L.
(b) Prove by induction that every string in L has exactly the same number of 0s and 1s.
(You may assume the identity #(a, x y) = #(a, x) + #(a, y) for any symbol a and any
strings x and y; see Exercise 5(b).)
13Models of Computation

Lecture 1: Strings [Sp’18](c) Prove by induction that L contains every string with the same number of 0s and 1s.

22. Recursively define a set L of strings over the alphabet {0, 1} as follows:• The empty string " is in L.
• For any strings x in L, the strings 0 x 1 and 1 x 0 are also in L.
• For any two strings x and y in L, the string x • y is also in L.
• These are the only strings in L.
(a) Prove that the string 01000110111001 is in L.
(b) Prove by induction that every string in L has exactly the same number of 0s and 1s.
(You may assume the identity #(a, x y) = #(a, x) + #(a, y) for any symbol a and any
strings x and y; see Exercise 5(b).)(c) Prove by induction that every string with the same number of 0s and 1s is in L.

23. Recursively define a set L of strings over the alphabet {0, 1, 2} as follows:• The empty string " is in L.
• For any string x in L, the string 0 x is also in L.
• For any strings x and y in L, the strings 1 x 2 y and 2 x 1 y are also in L.
• These are the only strings in L.
(a) Prove that the string 001201110220121220 is in L.
(b) For any string w ∈ {0, 1, 2}∗ , let ModThree(w ) denote the sum of the digits of w
modulo 3. This function can be defined recursively as follows:
0
if w = "ModThree(x)if w = 0 x
ModThree(w) =(ModThree(x) + 1) mod 3 if w = 1 x(ModThree(x) + 2) mod 3 if w = 2 x
For example, ModThree(2211) = 0 and ModThree(001201110220121220) = 0.
Prove that ModThree(w) = 0 for every string in w ∈ L.
(c) Find a string w ∈ {0, 1, 2}∗ such that ModThree(w) = 0 but w 6∈ L. Prove that youranswer is correct.
(d) Prove that #(1, w) = #(2, w) for every string w ∈ L.
(e) Find a string w ∈ {0, 1, 2}∗ such that #(1, w) = #(2, w) but w 6∈ L. Prove that youranswer is correct.
(f) Prove that L = w ∈ {0, 1, 2}∗ ModThree(w) = 0 and #(1, w) = #(2, w) .

24. A palindrome is a string that is equal to its reversal.
14Models of Computation

Lecture 1: Strings [Sp’18](a) Give a recursive definition of a palindrome over the alphabet Σ.
(b) Prove that any string p meets your recursive definition of a palindrome if and only if
p = pR .
(c) Using your recursive definition, prove that the strings w • wR and w • a • wR are
palindromes, for every string w and symbol a.
(d) Using your recursive definition, prove that p n is a palindrome for every palindrome pand every natural number n. (See Exercise 7.)(e) Using your recursive definition, prove that for every palindrome p, there is at mostone symbol a such that #(a, p) is odd. (See Exercise 5.)

25. A string w ∈ Σ∗ is called a shuffle of two strings x, y ∈ Σ∗ if at least one of the following
recursive conditions is satisfied:• w = x = y = ".
• w = aw0 and x = a x 0 and w0 is a shuffle of x 0 and y, for some a ∈ Σ and some
w0 , x 0 ∈ Σ∗ .
• w = aw0 and y = a y 0 and w0 is a shuffle of x and y 0 , for some a ∈ Σ and some
w0 , y 0 ∈ Σ∗ .
For example, the string BANANANANASA is a shuffle of the strings BANANA and ANANAS.
(a) Prove that if w is a shuffle of x and y, then |w| = |x| + | y|.
(b) Prove that w is a shuffle of x and y if and only if wR is a shuffle of x R and y R .

26. For any positive integer n, the Fibonacci string Fn is defined recursively as follows:
if n = 1,
0
Fn = 1
if n = 2,F•Fotherwise.
n−2

n−1

For example, F6 = 10101101 and F7 = 0110110101101.
(a) Prove that for every integer n ≥ 2, the string Fn can also be obtained from Fn−1 byreplacing every occurrence of 0 with 1 and replacing every occurrence of 1 with 01.
More formally, prove that Fn = Finc(Fn−1 ), where
if w = ""
Finc(w) = 1 · Finc(x)if w = 0 x01 • Finc(x) if w = 1 x[Hint: First prove that Finc(x • y) = Finc(x) • Finc( y).](b) Prove that the Fibonacci string Fn begins with 1 if and only if n is even.
(c) Prove that 00 is not a substring of any Fibonacci string Fn .
(d) Prove that 111 is not a substring of any Fibonacci string Fn .
15

Models of Computation

Lecture 1: Strings [Sp’18]? (e)Prove that 01010 is not a substring of any Fibonacci string Fn .

? (f)Find another string w that is not a substring of any Fibonacci string Fn , such that 00
and 111 and 01010 are not substrings of w.

Æ(g) Find a set of strings F with the following properties:• No string in F is a substring of any Fibonacci string Fn .
• No string in F is a proper substring of any other string in F .
• For all strings x ∈ {0, 1}∗ , if x has no substrings in F , then x is a substring ofsome Fibonacci string Fn .

Æ

? 27.

(h) Prove that the reversal of each Fibonacci string is a substring of another Fibonacci
string. More formally, prove that for every integer n ≥ 0, the string FnR is a substringof Fm for some integer m ≥ n.

Prove that the following three properties of strings are in fact identical.
• A string w ∈ {0, 1}∗ is balanced if it satisfies one of the following conditions:– w = ",
– w = 0 x 1 for some balanced string x, or– w = x y for some balanced strings x and y.
• A string w ∈ {0, 1}∗ is erasable if it satisfies one of the following conditions:– w = ", or– w = x 01 y for some strings x and y such that x y is erasable. (The strings x andy are not necessarily erasable.)• A string w ∈ {0, 1}∗ is conservative if it satisfies both of the following conditions:– w has an equal number of 0s and 1s, and– no prefix of w has more 0s than 1s.
(a) Prove that every balanced string is erasable.
(b) Prove that every erasable string is conservative.
(c) Prove that every conservative string is balanced.
[Hint: To develop intuition, it may be helpful to think of 0s as left brackets and 1s asright brackets, but don’t invoke this intuition in your proofs.]? 28.

A string w ∈ {0, 1}∗ is equitable if it has an equal number of 0s and 1s.
(a) Prove that a string w is equitable if and only if it satisfies one of the following
conditions:• w = ",
• w = 0 x 1 for some equitable string x,• w = 1 x 0 for some equitable string x, or• w = x y for some equitable strings x and y.
16Models of Computation

Lecture 1: Strings [Sp’18](b) Prove that a string w is equitable if and only if it satisfies one of the following
conditions:• w = ",
• w = x 01 y for some strings x and y such that x y is equitable, or• w = x 10 y for some strings x and y such that x y is equitable.
In the last two cases, the individual strings x and y are not necessarily equitable.
(c) Prove that a string w is equitable if and only if it satisfies one of the following
conditions:• w = ",
• w = x y for some balanced string x and some equitable string y, or• w = x R y for some for some balanced string x and some equitable string y.
(See the previous exercise for the definition of “balanced”.)© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

17