GATE CS 2003 Q39 — Sets, Relations and Functions

To find which number represents a valid encoding $h(\langle s_1, …, s_n \rangle)$, let us analyze the definitions of $f(s)$ and $h$:

1. For any non-empty string $s = a_1 a_2 \dots a_r$, the encoding is defined as: $$f(s) = p_1^{g(a_1)} p_2^{g(a_2)} \dots p_r^{g(a_r)} = 2^{g(a_1)} 3^{g(a_2)} \dots p_r^{g(a_r)}$$ where $g(a_i) \in \{3, 5, 7, 9, 11\}$. Thus, the exponent of each prime factor in $f(s)$ must belong to the set $\{3, 5, 7, 9, 11\}$.
2. The sequence encoding is defined as: $$h(\langle s_1, \dots, s_n \rangle) = 2^{f(s_1)} 3^{f(s_2)} \dots p_n^{f(s_n)}$$

The given options are all of the form $2^k 3^k 5^k$ for $k \in \{7, 8, 9, 10\}$. For $h(\langle s_1, s_2, s_3 \rangle) = 2^k 3^k 5^k$, we must have: $$f(s_1) = f(s_2) = f(s_3) = k$$ Let us test which value of $k$ can be a valid $f(s)$ for some string $s \in \Sigma^+$:

• For $k = 8$: We can write $8 = 2^3$. Since $3 \in \{3, 5, 7, 9, 11\}$, this matches the definition of $f(s)$ for a single-character string $s = a$ (where $g(a) = 3$). Thus, $f(a) = 2^{g(a)} = 2^3 = 8$.
  Choosing $s_1 = s_2 = s_3 = a$, we get: $$h(\langle a, a, a \rangle) = 2^{f(a)} 3^{f(a)} 5^{f(a)} = 2^8 3^8 5^8$$ This is a valid encoding.
• For other options:
  • $k = 7 = 7^1$ (exponents must be in $\{3, 5, 7, 9, 11\}$ and prime factors must start with $2$).
  • $k = 9 = 3^2$ (exponent $2$ is invalid, and prime $2$ is missing).
  • $k = 10 = 2^1 \cdot 5^1$ (exponents are $1$, which is invalid).