7.5. Induction in Computer Science 181
right bracket. For example, here are the counts for two sample strings:
[ ] ] [ [ [ [ [ ] ] ] ]
0 1 0 1 0 1 2 3 4 3 2 1 0[ [ [ ] ] [ ] ] [ ]
0 1 2 3 2 1 2 1 0 1 0A string has agood countif its running count never goes negative and ends with 0.
So the second string above has a good count, but the first one does not because its
count went negative at the third step. Let
GoodCountWWDfs2f];[gjshas a good countg:
The empty string has a length 0 running count we’ll take as a good count by
convention, that is, 2 GoodCount. The matched strings can now be characterized
precisely as this set of strings with good counts.
(a)Prove that GoodCount contains RecMatch by structural induction on the defi-
nition of RecMatch.
(b)Conversely, prove that RecMatch contains GoodCount.Hint: By induction on the length of strings in GoodCount. Consider when the
running count equals 0 for the second time.
Problems for Section 7.3
Homework Problems
Problem 7.12.
Ackermann’s function,AWN^2 !N, is defined recursively by the following rules:
A.m;n/WWD2n; ifmD 0 orn 1 (A-base)
A.m;n/WWDA.m 1;A.m;n 1//; otherwise: (AA)
Prove that ifBWN^2 !Nis a partial function that satisfies this same definition,
thenBis total andBDA.
Problems for Section 7.4
Practice Problems
Problem 7.13. (a)Write out the evaluation of
eval.subst.3x;x.x 1//;2/