Recursive decomposition

$($a$)$ A binary string is a palindrome if it reads the same forwards and backwards. Examples

of palindromes are $01100110,01010,.$

Let $P$ be the set of all binary strings that are palindromes. Give a recursive decompo$-$

sition for $P,$ with a brief explanation. Then use it to determine the generating series

for $P$ with respect to length.

$($b$)$ Let $A$ be the set of all binary strings that do not contain $0110011001$ as a substring.

Let $B$ be the set of all binary strings with exactly one copy of $0110011001,$ at the right

end. Write down two equations relating A and $B$ using the techniques shown in class,

with a brief explanation. Then use them to determine the generating series for A with

respect to length.