Give a recursive definition for each subset of the binary strings. A string x should be...

 

Transcribed Image Text:

Give a recursive definition for each subset of the binary strings. A string x should be in the recursively defined set if and only if x has the property described. (a) The set S consists of all strings with an even number of 1's. (b) The set S is the set of all binary strings that are palindromes. A string is a palindrome if it is equal to its reverse. For example, 0110 and 11011 are both palindromes. (c) The set S consists of all strings that have the same number of 0's and 1's. 4. (10 points) The set of full binary trees is defined recursively in Definition 5 on page 353: (1.) Basis step: A single vertex r is a rooted tree. (2.) Recursive step: If T and T are disjoint full binary trees, there is a full binary tree, denoted by T T2, consisting of a (new) root r together with edges connecting this root to the roots of the left subtree T and the right subtree T. 2 The book includes these pictures of the full binary trees that can be built up by applying the recursive step one or two times. (a.) Draw all the binary trees that could be built up by applying the recursive step three times. (b.) Come up with a formula for the maximum number of nodes (vertices) in a full binary tree that is built up by applying the recursive step n times. Prove your formula using mathematical induction. Give a recursive definition for each subset of the binary strings. A string x should be in the recursively defined set if and only if x has the property described. (a) The set S consists of all strings with an even number of 1's. (b) The set S is the set of all binary strings that are palindromes. A string is a palindrome if it is equal to its reverse. For example, 0110 and 11011 are both palindromes. (c) The set S consists of all strings that have the same number of 0's and 1's. 4. (10 points) The set of full binary trees is defined recursively in Definition 5 on page 353: (1.) Basis step: A single vertex r is a rooted tree. (2.) Recursive step: If T and T are disjoint full binary trees, there is a full binary tree, denoted by T T2, consisting of a (new) root r together with edges connecting this root to the roots of the left subtree T and the right subtree T. 2 The book includes these pictures of the full binary trees that can be built up by applying the recursive step one or two times. (a.) Draw all the binary trees that could be built up by applying the recursive step three times. (b.) Come up with a formula for the maximum number of nodes (vertices) in a full binary tree that is built up by applying the recursive step n times. Prove your formula using mathematical induction.