Question

1. Recall that the set {0,1}∗ is the set of all finite-length binary strings. Let f:{0,1}∗→{0,1}∗ to be f(x1x2…xk)=x2x3…xkx1. That is, f takes the first bit of a string x and moves it to the end of x, so for example a string 100becomes 001; if |x|≤1, then f(x)=x Also, suppose that g:{0,1}∗→{0,1}∗ is a function such that g(x1…xk)=0x1…xk (that is, gg puts an extra 0 in front of the given string, so for example g(100)=0100. Everywhere in this question we will refer to these f and g.
   1. Then  f(0011010)= and f(1)=
   2. Then g(000)=andg(1)=
   3. Then f−1(0011010)=
   4. Is f one-to-one? Is it onto? Is it a bijection?
   5. Is g one-to-one? Onto? Bijection?
   6. Calculate f(g(100101)) and g(f(100101)).
   7. Which of the following is true for these ff and gg? Justify your answer.
      1. ∀x∈{0,1}∗,f(g(x))=g(f(x))
      2. ∀x∈{0,1}∗,f(g(x))≠g(f(x))
      3. Neither

Answer 1