Mathematics for Computer Science

Chapter 7 Recursive Data Types178

Figure 7.2 Constructing the Koch Snowflake.

Prove by structural induction that the area inside any Koch snowflake is of the
formq

p

3 , whereqis a rational number.

Problems for Section 7.2

Practice Problems

Problem 7.8. (a)To prove that the set RecMatch, of matched strings of Defini-
tion 7.2.1 equals the set AmbRecMatch of ambiguous matched strings of Defini-
tion 7.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/.

(c)The recursive definition AmbRecMatch is ambiguous because it allows the
s
tconstructor 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 thes
tconstructor
whens¤andt¤.