If x is a string, then xR is the reverse of the string. For example, if x = 1011, then xR = 1101. A string is a palindrome if the string is the same backwards and forwards (i. e., if x = xR). Let B = {0, 1}. The set Bn is the set of all n-bit strings. Let Pn be the set of all strings in Bn that are palindromes.

(c) Determine the cardinality of P7 by showing a bijection between P7 and Bn for some n.

Answer explained below

Explanation:

Credit to Jordan Johnson,

The set Bn contains all binary strings of size n. The number of strings in the set is equal to 2n since there are n positions to fill and each position can be filled with either 0 or 1.

Therefore, total number of strings = 2 * 2 * ... * 2 = 2n

The set Pn that contains all the n-bit strings that are palindrome is a subset of the set Bn.

(c)

The set P7 contains 7-bit binary strings that are a palindrome. Each bit can either be 0 or 1 and hence there are 2 ways to fill each position of the binary string. The number of strings in P7can be computed as follows:

The first bit should be equal to the seventh bit. Number of ways to fill the first bit = 2 ways

The second bit should be equal to the sixth bit. Number of ways to fill the second bit = 2 ways

The third bit should be equal to the fifth bit. Number of ways to fill the third bit = 2 ways

The fourth bit could either be 0 or 1. Number of ways to fill the fourth bit = 2 ways

Therefore, the cardinality of P7 is equal to the total number of ways to fill the first 4 bits of the 7-bit strings = 2*2*2*2 = 16

To create a bijection function between P7 and Bn, compute the value of n as shown below:

Number of strings in P7 = Number of strings in Bn

16 = 2n

24 = 2n

Therefore, the value of n = 4.

The string in the set B4 are as follows:

{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}

Proof for bijection:

1. The above function P7 to B4 is one-one or injective, that is, if f (x) = f (y), then x = y where x, y belongs to the set P7.

For all x and y belonging to set P7, there are no two strings x and y for which f (x) = f (y), where x is not equal to y.

Hence, the function is one-one or injective.

2. The above function is onto or surjective, that is, for all y belonging to B4, there exist f (x) such that f (x) = y.

In other words, there is no y that belongs to B4 which is not mapped to an element of the set P7. None of the element in the set B4 is left un-mapped.

Hence, the function is onto or surjective.

Since the function is injective and surjective, the function P7 to B4 is bijective.

Hence, proved.