1. Consider palindromes that consist only of lowercase letters, such as “level” and “deed,” but not “RadaR,” “ADA,” or “101.” Let c ( n ) be the number of palindromes of length n .
a. Write a recursive definition of c ( n ).
b. Prove that your answer to part a is correct by using mathematical induction.
2. Prove the following for single-letter operands: If E is a prefix expression and Y is a nonempty string of nonblank characters, then E Y cannot be a legal prefix expression. ( Hint: Use a proof by induction on the length of E .)
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here