7.5. Induction in Computer Science 179
Class Problems
Problem 7.9.
Letpbe the string[ ]. A string of brackets is said to beerasableiff it can be
reduced to the empty string by repeatedly erasing occurrences ofp. For example,
here’s how to erase the string[ [ [ ] ] [ ] ] [ ]:
[ [ [ ] ] [ ] ] [ ]![ [ ] ]![ ]!:On the other hand the string[ ] ] [ [ [ [ [ ] ]is not erasable because when we try to
erase, we get stuck:
[ ] ] [ [ [ [ [ ] ]!] [ [ [ [ ]!] [ [ [6!
Let Erasable be the set of erasable strings of brackets. Let RecMatch be the
recursive data type of strings ofmatchedbrackets given in Definition 7.2.1.
(a)Use structural induction to prove that
RecMatchErasable:(b)Supply the missing parts of the following proof that
ErasableRecMatch:Proof.We prove by strong induction that every length-nstring in Erasable is also
in RecMatch. The induction hypothesis is
P.n/WWD8x 2 Erasable:jxjDnIMPLIESx 2 RecMatch:Base case:
What is the base case? Prove thatPis true in this case.Inductive step: To proveP.nC1/, supposejxj DnC 1 andx 2 Erasable. We
need to show thatx 2 RecMatch.
Let’s say that a stringyis aneraseof a stringziffyis the result of erasing asingle
occurrence ofpinz.
Sincex 2 Erasable and has positive length, there must be an erase,y 2 Erasable,
ofx. Sojyj Dn 1 0 , and sincey 2 Erasable, we may assume by induction
hypothesis thaty 2 RecMatch.
Now we argue by cases:
Case(yis the empty string):
Prove thatx 2 RecMatch in this case.
Case(yD[s]tfor some stringss;t 2 RecMatch): Now we argue by subcases.