Chapter 7 Recursive Data Types180
Subcase(xis of the form[s^0 ]twheresis an erase ofs^0 ):
Sinces 2 RecMatch, it is erasable by part (b), which implies thats^02
Erasable. Butjs^0 j< jxj, so by induction hypothesis, we may assume that
s^02 RecMatch. This shows thatxis the result of the constructor step of
RecMatch, and thereforex 2 RecMatch.
Subcase(xis of the form[s]t^0 wheretis an erase oft^0 ):
Prove thatx 2 RecMatch in this subcase.
Subcase(xDp[s]t):
Prove thatx 2 RecMatch in this subcase.Are there any remaining subcases? If so list those. If not, explain why the
above cases are sufficient.
This completes the proof by strong induction onn, so we conclude thatP.n/holds
for alln 2 N. Thereforex 2 RecMatch for every stringx 2 Erasable. That is,
ErasableRecMatch. Combined with part (a), we conclude that
ErasableDRecMatch:Problem 7.10. (a)Prove that the set RecMatch, of matched strings of Definition 7.2.1
is closed under string concatenation. Namely, ifs;t 2 RecMatch, thenst 2
RecMatch.
(b)Prove AmbRecMatchRecMatch, where AmbRecMatch is the set of am-
biguous matched strings of Definition 7.2.2.
(c)Prove that RecMatchDAmbRecMatch.Problem 7.11.
One way to determine if a string has matching brackets, that is, if it is on the set,
RecMatch, of Definition 7.2.1 is to start with 0 and read the string from left to right,
adding 1 to the count for each left bracket and subtracting 1 from the count for each