6.2. Strings of Matched Brackets 177
Constructor case:
#c.ha;si/WWD
(
#c.s/ ifa¤c;
1 C#c.s/ ifaDc:
We’ll need the following lemma in the next section:
Lemma 6.1.6.
#c.st/D#c.s/C#c.t/:
The easy proof by structural induction is an exercise (Problem 6.7).
6.2 Strings of Matched Brackets
Letf];[gbe the set of all strings of square brackets. For example, the following
two strings are inf];[g:
[ ] ] [ [ [ [ [ ] ] and [ [ [ ] ] [ ] ] [ ] (6.1)
A string,s 2 f];[g, is called amatched stringif its brackets “match up” in
the usual way. For example, the left hand string above is not matched because its
second right bracket does not have a matching left bracket. The string on the right
is matched.
We’re going to examine several different ways to define and prove properties
of matched strings using recursively defined sets and functions. These properties
are pretty straightforward, and you might wonder whether they have any particular
relevance in computer science. The honest answer is “not much relevanceany
more.” The reason for this is one of the great successes of computer science, as
explained in the text box below.
