November 8, 2000 November 8, 2000

This is the last lecture explicitly dedicated to mathematical induction. Compilers invariably check that the parentheses in expressions are balanced and return error messages if they are not. How might they check?

Let P be the set of strings of parentheses. Define a function N: P Z recursively as follows:

N.l > = 0.
N.( = 1.
N.) = -1.
N.mn = N.m+ N.n.

Note that it is necessary to prove that if mn = mn then N.m+ N.n = N.m+ N.n. This is left as an exercise. An alternative would be to define N recursively by N.ml = N.m, N.m( = N.m+1, and N.m) = N.m-1.

As an example observe that N.(()(() = 1+1-1+1 +1 -1 = 2.

We have the following necessary and sufficient condition for w P to be balanced.

Theorem: w P is balanced if and only if N.w = 0 and N.m 0 whenever m is a prefix of w.

Proof: The proof of necessity proceeds by induction on the length of w. Assume w is balanced. If w = l we have N.w = 0 and the only prefixes of l are l itself. Otherwise we have either w = (m) for some balanced m or we have w = mn for some balanced m and n both shorter than w.

In the first case since m is balanced (and shorter than w) it is clear that N.w = N.(m) = 1 +0 -1 = 0. The prefixes of (m) are of the form l, (m where m is a prefix of m, and (m). It is easy to verify in each case that N takes a non-negative value on each of them.

In the second case, since m and n are balanced and shorter than w we have N.w = N.mn = N.m+ N.m = 0 + 0 = 0. The prefixes of mn are either prefixes of m or of the form mn with n a prefix of n. Again it is easy to verify that N takes a non-negative value on each of them.

For necessity we proceed as before by induction on the length of w. If w is l then it is balanced. We distinguish two cases.

If there is a prefix m of w other than l or w for which N.m = 0. In this case write w = mn and observe that both m and n are shorter than w and their prefixes satisfiy the condition on N. Then both m and n are balanced and so is w.

If there is no such prefix of w observe that the first character in w must be (. Write w = (mc where c is the last character of w. Since N.(m > 0, and N.w = 0 of necessity c is ) and w = (m). Now m is shorter than w and satisfies the condition on N. Then m is balanced and w = (m) is balanced as required.


File translated from TEX by TTH, version 2.60.
On 8 Nov 2000, 16:25.