Answer Happy

Complete all questions (d) - (f) for the "A Nut for a
Jar of Tuna" exercise. If illustrations are necessary to complete
the work, please include.
W 4. A Nut for a Jar of Tuna On Binary Island, the locals have only two letters in their alphabet: A and B. Sequences of these letters are called strings. The number of letters in a string is called its length. If a string has length n, then we call it an n-string. For example, ABAABABAABAA is a 12-string. A block of consecutive letters in a string is called a substring. A substring may appear more than once. For example, ABAABABAABAA contains the substring AA three times, the substrings AB and BA four times each, but does not contain the substring BB. A string that reads the same forwards and backwards is called palindromic. Every 3-string starting with A has exactly three different palindromic substrings, as shown in this table. 3-string palindromic substrings AAA AAB ABA ABB A, AA, AAA A, B, AA A, B, ABA A, B, BB (d) Find an 8-string that starts with AABBA and has only 7 palindromic substrings. (e) Show that every n-string has at most n distinct palindromic sub- strings. (f) Show that there are arbitrarily long strings with only 8 distinct palin- dromic substrings.