展开查看详情
1 .Recursive Definitions and Structural Induction 2/21/12 1
2 .Recursive Definitions Common way of defining mathematical objects Base case(s ) Constructor rule(s ) “Nothing else” (generally implicit) Have already seen recursive definition of the Fibonacci numbers F 0 =0, F 1 =1 F n +1 = F n +F n-1 ( n ≥ 1) 2/21/12 2
3 .The set of all strings of balanced parentheses () , (()()) , ()() but not )( or (() Familiar “Counting rule”—an algorithm: Start count at 0 When you see a “ ( “, add 1 When you see a “ ) ”, subtract 1 Balanced if count never goes negative and ends at 0 But we want a structural definition 2/21/12 3
4 .A Structural Definition Base case: The empty string εis balanced Constructor rules: C1: If x is balanced then so is ( x ) , that is, the result of writing a “ ( “, then x , then “ ) ” C2: If x and y are balanced then so is xy (Implicit “that’s - all” clause) (No string is balanced unless it can be constructed using the base and constructor rules) NB: x and y are variables whose values are strings 2/21/12 4
5 .Some Balanced Strings ε : Base case ( ) : C1 rule, ( x ) , where x = ε (( )) : C1 rule, ( x ) , where x = ( ) ( )( ) : C2 rule, xy , where x = y = ( ) (( ))( )( ) : C2 rule, xy , where x = (( ) ) , y = ( )( ) … 2/21/12 5
6 .Showing a String is Balanced Is ( ( )( ) ) balanced? Yes, because ε is balanced (base rule) ( ε ) is balanced by first constructor rule, but that is just another way of writing () ( )( ) is balanced by second constructor rule ( ( )( ) ) is balanced by first constructor rule 2/21/12 6
7 .Proof that every balanced string has equal numbers of “ ( “ and “ ) ” Suppose x is balanced. Then it is balanced because of either the base rule or a constructor rule If by the base rule , then x is ε and has 0 left and 0 right parentheses. ✓ If by the first constructor rule then x = ( y ) for some previously constructed balanced string y . Then y has the same number of “ ( “ and “ ) ”, say n . Then x = ( y ) has one more “ ( “ and one more “ ) ”, so n +1 of each. ✓ 2/21/12 7
8 .Every balanced string has equal numbers of “(“ and “)” If by the second constructor rule then x = yz for some previously constructed balanced strings y and z . Then y has the same number of “ ( ” and “ ) ”, say n , and z has the same number of “ ( ” and “ ) ”, say m . Then x = yz has m + n “ ( ” and m + n “ ) ”. ✓ 2/21/12 8
9 .Structural Induction: The General Schema To prove P( x ) holds for all x in a recursively defined set S , prove P(b ) for each base case b∈ S P(c( x 1 ,…, x k )) for each constructor c , assuming as the induction hypothesis that P( x 1 ), …, and P( x k ) all hold. 2/21/12 9
10 .Use Caution if Constructions are Not Unique! A funny string is defined by these rules: The strings ε , a, and b are funny If x and y are funny then so is xyy The funniness f(z ) of a funny string x is 0 if z = ε 1 if z = a or b f(x)+f(y ) if z = xyy per the constructor rule What is f(aabbbb )? 2/21/12 10
11 .Use Caution if Constructions are Not Unique! aa is funny ( x = ε , y =a). So is bb aabbbb is funny: ( aa)[(bb)(bb )] = xyy ( x = aa , y =bb) What is f(aabbbb ) = f(aa)+f(bb )? f(aa ) = f(ε)+f(a ) = 1 = f(bb ) f(aabbbb ) = f(aa)+f(bb ) = 2 BUT aabb is also funny: ( aa)(b)(b ) aabbbb = x’y’y ’ = [ aabb]bb ( x ’= aabb , y ’= b ) f(aabbbb ) = f(aabb)+f(b ) = f(aa)+f(b)+f(b ) = 3! 2/21/12 11
热门城市
