Question

In: Advanced Math

Recall that the set {0,1}∗ is the set of all finite-length binary strings. Let f:{0,1}∗→{0,1}∗ to...

  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

Solutions

Expert Solution

Colby Messinger answered 2 years ago
Next > < Previous

Related Solutions

Prove or Disprove The set of all finite strings is undecidable. The set of all finite...
Prove or Disprove The set of all finite strings is undecidable. The set of all finite strings is recognizable
1. Write a Post system that defines the set of binary strings of odd length that...
1. Write a Post system that defines the set of binary strings of odd length that have a “x” as the middle character and "x" is a string
Design an FA (Finite automaton) and RE to accept the set of all strings over the...
Design an FA (Finite automaton) and RE to accept the set of all strings over the alphabet {0,1} which contains even number of 0's and odd number of 1's.
Let X be the set of all subsets of R whose complement is a finite set...
Let X be the set of all subsets of R whose complement is a finite set in R: X = {O ⊂ R | R − O is finite} ∪ {∅} a) Show that T is a topological structure no R. b) Prove that (R, X) is connected. c) Prove that (R, X) is compact.
Let f : [0, 1] → R and suppose that, for all finite subsets of [0,...
Let f : [0, 1] → R and suppose that, for all finite subsets of [0, 1], 0 ≤ x1 < x2 < · · · < xn ≤ 1, we have |f(x1) + f(x2) + · · · + f(xn)| ≤ 1. Let S := {x ∈ [0, 1] : f(x) ̸= 0}. Show that S is countable
2. Let A = {1,2,3,4}. Let F be the set of all functions from A to...
2. Let A = {1,2,3,4}. Let F be the set of all functions from A to A. Recall that IA ∈ F is the identity function on A given by IA(x) = x for all x ∈ A. Consider the function E : F → A given by E(f) = f(1) for all f ∈ F. (a) Is the function E one-to-one? Prove your answer. (b) Is the function E onto? Prove your answer. (c) How many functions f ∈...
write the dfa for Let L={w in {0,1}*| w is a binary number that is a...
write the dfa for Let L={w in {0,1}*| w is a binary number that is a multiple of 4}
Suppose that you pick a bit string from the set of all bit strings of length...
Suppose that you pick a bit string from the set of all bit strings of length ten. Find the probability that the bit string has exactly two 1s; the bit string begins and ends with 0; the bit string has the sum of its digits equal to seven; the bit string has more 0s than 1s; the bit string has exactly two 1s, given that the string begins with a 1.
Suppose that you pick a bit string from the set of all bit strings of length...
Suppose that you pick a bit string from the set of all bit strings of length ten. Find the probability that the bit string has exactly two 1s; the bit string begins and ends with 0; the bit string has the sum of its digits equal to seven; the bit string has more 0s than 1s; the bit string has exactly two 1s, given that the string begins with a 1.
Let Ω be any set and let F be the collection of all subsets of Ω...
Let Ω be any set and let F be the collection of all subsets of Ω that are either countable or have a countable complement. (Recall that a set is countable if it is either finite or can be placed in one-to-one correspondence with the natural numbers N = {1, 2, . . .}.) (a) Show that F is a σ-algebra. (b) Show that the set function given by μ(E)= 0 if E is countable ; μ(E) = ∞ otherwise...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT