Mathematics for Computer Science

Chapter 6 Recursive Data Types196

 F 2 :

– 52 F 2 ,

• ifn;m 2 F 1 , thennm 2 F 2.

(a)Show that one of these definitions is technicallyambiguous. (Remember that
“ambiguous recursive definition” has a technical mathematical meaning which does
not imply that the ambiguous definition is unclear.)

(b)Briefly explain what advantage unambiguous recursive definitions have over
ambiguous ones.

(c)A way to prove thatF 1 DF 2 , is to show firat thatF 1 F 2 and second that
F 2 F 1. One of these containments follows easily by structural induction. Which
one? What would be the induction hypothesis? (You do not need to complete a
proof.)

Problem 6.13. (a)To prove that the set RecMatch, of matched strings of Defini-
tion 6.2.1 equals the set AmbRecMatch of ambiguous matched strings of Defini-
tion 6.2.2, you could first prove that

8 r 2 RecMatch: r 2 AmbRecMatch;

and then prove that

8 u 2 AmbRecMatch: u 2 RecMatch:

Of these two statements, circle the one that would be simpler to prove by structural
induction directly from the definitions.

(b)Suppose structural induction was being used to prove that AmbRecMatch
RecMatch. Circle the one predicate below that would fit the format for a structural
induction hypothesis in such a proof.

P 0 .n/WWDjsjnIMPLIESs 2 RecMatch.

P 1 .n/WWDjsjnIMPLIESs 2 AmbRecMatch.

P 2 .s/WWDs 2 RecMatch.

P 3 .s/WWDs 2 AmbRecMatch.

P 4 .s/WWD.s 2 RecMatchIMPLIESs 2 AmbRecMatch/.