6.5. Induction in Computer Science 197
(c)The recursive definition AmbRecMatch is ambiguous because it allows the
stconstructor to apply whensortis the empty string. But even fixing that,
ambiguity remains. Demonstrate this by giving two different derivations for the
string ”[ ] [ ] [ ]according to AmbRecMatch but only using thestconstructor
whens¤andt¤.
Class Problems
Problem 6.14.
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 6.2.1
(a)Use structural induction to prove thatRecMatchErasable:(b)Supply the missing parts (labeled by “(*)”) of the following proof thatErasableRecMatch:Proof.We prove by strong induction that every lengthnstring 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.