Exercises: 1. Using the fact that 3x2 +7x – 9 = (((((3)x) + 7)x) – 9), show how to produce this polynomial from the rules for POLYNOMIAL using multiplication only twice. What is the smallest number of...

answer no 3

Extracted text: Exercises: 1. Using the fact that 3x2 +7x – 9 = (((((3)x) + 7)x) – 9), show how to produce this polynomial from the rules for POLYNOMIAL using multiplication only twice. What is the smallest number of steps needed for producing x* + xª? 2. Show that if n is less than 31, then xn can be shown to be in POLYNOMIAL in fewer than eight steps. 3. What is the full list of substrings of length 2 that cannot occur in arithmetic expressions? 4. The rules given for the set AĚ allow for the peculiar expressions (((((9))))) and -(-(-(-(9)))). These are not harmful, but is there some modified definition of AE that eliminates this problem? Exercises: 5. Give a recursive definition for the language EVENPALINDROME of all palindromes of even length. 6. Give a recursive definition for the set POWERS-OF-TWO = {1 2 4 8 16 ....} and use your definition to prove that the product of two POWERS-OF-TWO is also a POWER-OF-TWO.