Mathematics for Computer Science
6 Recursive Data Types Recursive data typesplay a central role in programming, and induction is really all about them. Recursive ...
Chapter 6 Recursive Data Types174 Definition 6.1.1.LetAbe a nonempty set called analphabet, whose elements are referred to ascha ...
6.1. Recursive Definitions and Structural Induction 175 Definition 6.1.3.Theconcatenationstof the stringss;t 2 Ais defined rec ...
Chapter 6 Recursive Data Types176 Constructor case: SupposesWWDha;riand assume the induction hypothesis,P.r/. We must show thatP ...
6.2. Strings of Matched Brackets 177 Constructor case: #c.ha;si/WWD ( #c.s/ ifa¤c; 1 C#c.s/ ifaDc: We’ll need the following lemm ...
Chapter 6 Recursive Data Types178 Expression Parsing During the early development of computer science in the 1950’s and 60’s, cr ...
6.2. Strings of Matched Brackets 179 Now, [] [ ]D[ ] [ ] 2 RecMatch (lettingsD;tD[ ]) [ [ ] ]D[ [ ] ] 2 RecMatch (lettingsD[ ...
Chapter 6 Recursive Data Types180 Definition 6.2.2.Define the set, AmbRecMatchf];[grecursively as follows: Base case: 2 Amb ...
6.3. Recursive Functions on Nonnegative Integers 181 6.3.1 Some Standard Recursive Functions onN Example6.3.2. The factorial fun ...
Chapter 6 Recursive Data Types182 f 2 .n/WWD ( 0; ifnD0; f 2 .nC1/ otherwise: (6.3) This “definition” has a base case, but still ...
6.4. Arithmetic Expressions 183 but with a slow growing coefficient nearly equal to the inverse Ackermann func- tion. This means ...
Chapter 6 Recursive Data Types184 [ef] 2 Aexp. The expression[ef] is called aproduct. The Aexp’seandf are called thecomponent ...
6.4. Arithmetic Expressions 185 For example, here’s how the recursive definition of eval would arrive at the value of 3 Cx^2 whe ...
Chapter 6 Recursive Data Types186 Here’s how the recursive definition of the substitution function would find the result of subs ...
6.4. Arithmetic Expressions 187 Theorem 6.4.4.For all expressionse;f 2 Aexp andn 2 Z, eval.subst.f;e/;n/Deval.e;eval.f;n//: (6.2 ...
Chapter 6 Recursive Data Types188 by Definition 6.4.2.(6.11) of eval for a sum expression. By induction hypoth- esis (6.22), thi ...
6.5. Induction in Computer Science 189 Problems for Section 6.1 Class Problems Problem 6.1. Prove that for all stringsr;s;t 2 A ...
Chapter 6 Recursive Data Types190 (b)Prove by Structural Induction on this definition that the Elementary 18.01 Functions areclo ...
6.5. Induction in Computer Science 191 Thesize,jGj, ofG 2 binary-2PTG is defined recursively on this definition by: Base case: ...
Chapter 6 Recursive Data Types192 Homework Problems Problem 6.6. Letm;nbe integers, not both zero. Define a set of integers,Lm;n ...
«
5
6
7
8
9
10
11
12
13
14
»
Free download pdf
