Consider the language PALINDROME over the alphabet {a b}. (i) Prove that if x is in PALINDROME,

Question:

Consider the language PALINDROME over the alphabet {a b}.
(i) Prove that if x is in PALINDROME, then so is xn for any n.
(ii) Prove that if y3 is in PALINDROME, then so is y.
(iii) Prove that if zn is in PALINDROME for some n (greater than 0), then z itself is also.
(iv) Prove that PALINDROME has as many words of length 4 as it does of length 3.
(v) Prove that PALINDROME has as many words of length 2n as it has of length 2n - 1. How many words is that?

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question
Question Posted: