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

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 1 year 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 deﬁnes the set of binary strings of odd length that...

1. Write a Post system that deﬁnes the set of binary strings of odd length that have a “x” as the middle character and "x" is a string

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...

Create a Deterministic finite automaton that takes in binary strings and accepts them which has both...

Create a Deterministic finite automaton that takes in binary strings and accepts them which has both an odd number of zeros and a sum that is divisible by 3 (but no others). For example, 0111 should be accepted, but not 011 or 111.

Recall that a 5-bit string is a bit strings of length 5, and a bit string...

Recall that a 5-bit string is a bit strings of length 5, and a bit string of weight 3, say, is one with exactly three 1’s. a. How many 5-bit strings are there? b. How many 5-bit strings have weight 0? c. How many 5-bit strings have weight 1? d. How many 5-bit strings have weight 2? e. How many 5-bit strings have weight 4? f. How many 5-bit strings have weight 5? g. How many 5-bit strings have weight...

Subjects