Chapter III Recursive Definitions

Definition  Fibonacci sequence

Definition 	Positive integer powers of x

	Rule 1	x  POWERS

	Rule 2	If a e POWERS, then ax e POWERS.

	Rule 3	No other expressions are in POWERS.



Definition Polynomials in x

	Rule 1	Any number is in POLYNOMIALX

	Rule 2	x e POLYNOMIALX

	Rule 3	If p, q  e POLYNOMIALX then so are p + q, (q), and pq.

	Rule 4	No other expressions are in POLYNOMIALX.

Definition Polynomials in x and y

	Rule 2 becomes x, y  e POLYNOMIALXY.

Problem 15 Page 36

(i) Tell why the following recursive definition for PALINDROME over à = {a, b} is incorrect, and tell how to fix it.
		Rule 1	a, b  e PALINDROME.

		Rule 2	If x  e PALINDROME, then so are axa and bxb.

		Rule 3	No other strings are in PALINDROME.

(ii) Give a recursive definition for EVENPALINDROME, the set of palindromes of even length.


		Solution (i) The strings are all of odd length.  Add the strings of even length.  
To do this, add the shortest possible string of even length, namely ò, in Rule 1.


(ii) Change Rule 1 to read
	Rule 1	ò  e EVENPALINDROME.