Recursive definitions for subsets of binary strings. Give a recursive definition for the specified subset of the binary strings. A string r should be in the recursively defined set if and only if r has the property described. The set S is the set of all binary strings that are palindromes. A string is a palindrome if it is equal to its reverse. For example, 0110 and 11011 are both palindromes.

Step-by-step explanation:

A binary string with 2n+1 number of zeros, then you can get a binary string with 2n (+1) + 1 = 2n+3 number of zeros either by adding 2 zeros or 2 1's at any of the available 2n+2 positions. Way of making each of these two choices are (2n+2) 22. So, basically if b2n+12n+1 is the number of binary string with 2n+1 zeros then your

b2n+32n+3 = 2 (2n+2) 22 b2n+12n+1

your second case is basically the fact that if you have string of length n ending with zero than you can the string of length n+1 ending with zero by:

1. Either placing a 1 in available n places (because you can't place it at the end)

2. or by placing a zero in available n+1 places.

0 ϵ P

x ϵ P → 1x ϵ P, x1 ϵ P

x' ϵ P, x'' ϵ P → xx'x''ϵ P