5. (6 marks) Let S be the set of all binary strings of length 6. Consider the relation ρ on the set S in which for all a,b ∈ S, (a,b) ∈ ρ if and only if the length of a longest substring of consecutiv...
5. (6 marks) Let S be the set of all binary strings of length 6.
Consider the relation ρ on the set S in which for all a,b ∈ S,
(a,b) ∈ ρ if and only if the length of a longest substring of
consecutive ones in a is the same as the length of a longest
substring of consecutive ones in b.
(a) Is 011010 related to 000011? Explain why or why not.
(b) Prove that ρ is an equivalence relation.
(c) List the elements of the equivalence class [111100].
Homework Answers
(a) Yes, both the strings are related to each other.
The consecutive length of strings in the first case (011010) is 2, because of 2nd and 3rd 1's in consecutive order.
Similarly, the 000011 is 2, because of 5th and 6th 1's in consecutive order
(b) For the relation p to be an equivalence relation. It must be reflexive, symmetric and transitive in nature
Relation is said to be reflexive if (a,a) belongs to R
The statement is TRUE, since the number of consecutive 1's in the single string pattern will be same.
Relation is said to be symmetric, if (a,b) belongs to R, then (b,a) belongs to R
The statement is TRUE, since if (a,b) belongs to R, then it implies that number of consecutive 1's in both strings a and b are same.
Hence the relation is symmetric in nature
Relation is said to be transitive, if (a,b) and (b.c) belongs to R, then (a,c) belongs to R
The statement is TRUE, since if (a,b) and (b.c) belongs to R, then it implies that number of consecutive 1's in both strings a and b are same and number of consecutive 1's in both strings b and c are same, which implies the strings a and c also have same length of consecutive 1's
Hence the relation is symmetric in nature
(c) The equivalence class will have four consecutive 1's, hence the elements of the equivalence class will be
011110, 001111,111101,101111, 111100
Note - Post any doubts/queries in comments section.
Add Answer to:
5. (6 marks) Let S be the set of all binary strings of length 6. Consider the relation ρ on the set S in which for all a,b ∈ S, (a,b) ∈ ρ if and only if the length of a longest substring of consecutiv...
probelms 9.1 9 Modular arithmetic Definition 9.1 Let S be a set. A relation R =...
probelms 9.1
9 Modular arithmetic Definition 9.1 Let S be a set. A relation R = R(,y) on S is a statement about pairs (x,y) of elements of S. For r,y ES, I is related to y notation: Ry) if R(x,y) is true. A relation Ris: Reflexive if for any I ES, R. Symmetric if for any ry ES, Ry implies y Rr. Transitive if for any r.y.ES, Ry and yRimply R. An equivalence relation is a reflexive, symmetric and...
2. Let S 11,2,3,4,5, 6, 7,8,91 and let T 12,4,6,8. Let R be the relation on P (S) detined by for ...
2. Let S 11,2,3,4,5, 6, 7,8,91 and let T 12,4,6,8. Let R be the relation on P (S) detined by for all X, Y E P (s), (X, Y) E R if and only if IX-T] = IY-T]. (a) Prove that R is an equivalence relation. (b) How many equivalence classes are there? Explain. (c) How mauy elements of [ø], the equivalence class of ø, are there? Explain (d) How many elements of [f1,2,3, 4)], the equivalence class of (1,2,3,...
2. A binary string is a finite sequence u-діаг . . . an, where each ai is either 0 or 1. In this case n is the length o...
2. A binary string is a finite sequence u-діаг . . . an, where each ai is either 0 or 1. In this case n is the length of the string v. The strings ai, aia2,... ,ai... an-1,ai... an are all prefixes of v. On the set X of all binary strings consider the relations Ri and R2 defined as follows: Ri-(w, v) w and v have the same length ) R2 = {(u, v) I w is a prefix...
2. 9 marks] Strings. Consider the following definitions on strings Let U be the set of all strings Let s be a str...
2. 9 marks] Strings. Consider the following definitions on strings Let U be the set of all strings Let s be a string. The length or size of a string, denoted Is, is the number of characters in s Let s be a string, and i e N such that 0 < ί < sl. We write s[i] to represent the character of s at index i, where indexing starts at 0 (so s 0] is the first character, and...
2. 9 marks] Strings. Consider the following definitions on strings Let U be the set of all strings. Let s be a stri...
2. 9 marks] Strings. Consider the following definitions on strings Let U be the set of all strings. Let s be a string. The length or size of a string, denoted Is, is the number of characters in s Let s be a string, and ie N such that 0 Si< Is. We write si] to represent the character of s at index i, where indexing starts at 0 (so s(0 is the first character, and s|s -1 is the...
2. A binary string is a finite sequence v = a1a2 . . . an, where each ai is either 0 or 1. In this case n is the length...
2. A binary string is a finite sequence v = a1a2 . . . an, where each ai is either 0 or 1. In this case n is the length of the string v. The strings a1, a1a2, . . . , a1 . . . an−1, a1 . . . an are all prefixes of v. On the set X of all binary strings consider the relations R1 and R2 defined as follows: R1 = {(w, v) | w...
Let S be the set of binary strings defined recursively as follows: Basis step: 0ES Recursive step...
discrete math. Structural Induction: Please write and
explain clearly. Thank you.
Let S be the set of binary strings defined recursively as follows: Basis step: 0ES Recursive step: If r ES then 1rl E S and 0x0ES (I#x and y are binary strings then ry is the concatenation of and y. For instance, if 011 and y 101, then ry 011101.) (a) List the elements of S produced by te first 2 applications of the recursive definition. Find So, Si...
4. (10pts) Let S be the subset of the set of binary strings defined recursively by...
4. (10pts) Let S be the subset of the set of binary strings defined recursively by Basis: XES. Recursive rule: If ze S, then c0 € S, and 1.6 ES. List the elements of S produced by the recursive definition with length less than or equal to 3.
=(V, En) 5. Let n1 be an integer and define the graph Gn as follows {0,1}", the set of all binary strings of length...
=(V, En) 5. Let n1 be an integer and define the graph Gn as follows {0,1}", the set of all binary strings of length n. Vn = Two vertices x and y are connected by an edge emu if and only if x and y differs in exactly one position. (a) (4 points) Draw the graph Gn for n = 1,2,3 (b) (4 points) For a general n 2 1, find |Vn and |En (c) (10 points) Prove that for...
2. A binary string s a finite sequence u = ala2 . . . an, where each ai įs either 0 or 1. In this case n is the length...
2. A binary string s a finite sequence u = ala2 . . . an, where each ai įs either 0 or 1. In this case n is the length of the string v. The strings ai,aia2,...,ai...an-1,aan are all prefixes of v. On the set X of all binary strings consider the relations Ri and R2 defined as follows R, = {(u, u) | w and u have the same length } {(w, u) | w is a prefix of...
probelms 9.1
9 Modular arithmetic Definition 9.1 Let S be a set. A relation R = R(,y) on S is a statement about pairs (x,y) of elements of S. For r,y ES, I is related to y notation: Ry) if R(x,y) is true. A relation Ris: Reflexive if for any I ES, R. Symmetric if for any ry ES, Ry implies y Rr. Transitive if for any r.y.ES, Ry and yRimply R. An equivalence relation is a reflexive, symmetric and...
2. Let S 11,2,3,4,5, 6, 7,8,91 and let T 12,4,6,8. Let R be the relation on P (S) detined by for all X, Y E P (s), (X, Y) E R if and only if IX-T] = IY-T]. (a) Prove that R is an equivalence relation. (b) How many equivalence classes are there? Explain. (c) How mauy elements of [ø], the equivalence class of ø, are there? Explain (d) How many elements of [f1,2,3, 4)], the equivalence class of (1,2,3,...
2. A binary string is a finite sequence u-діаг . . . an, where each ai is either 0 or 1. In this case n is the length of the string v. The strings ai, aia2,... ,ai... an-1,ai... an are all prefixes of v. On the set X of all binary strings consider the relations Ri and R2 defined as follows: Ri-(w, v) w and v have the same length ) R2 = {(u, v) I w is a prefix...
2. 9 marks] Strings. Consider the following definitions on strings Let U be the set of all strings Let s be a string. The length or size of a string, denoted Is, is the number of characters in s Let s be a string, and i e N such that 0 < ί < sl. We write s[i] to represent the character of s at index i, where indexing starts at 0 (so s 0] is the first character, and...
2. 9 marks] Strings. Consider the following definitions on strings Let U be the set of all strings. Let s be a string. The length or size of a string, denoted Is, is the number of characters in s Let s be a string, and ie N such that 0 Si< Is. We write si] to represent the character of s at index i, where indexing starts at 0 (so s(0 is the first character, and s|s -1 is the...
discrete math. Structural Induction: Please write and
explain clearly. Thank you.
Let S be the set of binary strings defined recursively as follows: Basis step: 0ES Recursive step: If r ES then 1rl E S and 0x0ES (I#x and y are binary strings then ry is the concatenation of and y. For instance, if 011 and y 101, then ry 011101.) (a) List the elements of S produced by te first 2 applications of the recursive definition. Find So, Si...
4. (10pts) Let S be the subset of the set of binary strings defined recursively by Basis: XES. Recursive rule: If ze S, then c0 € S, and 1.6 ES. List the elements of S produced by the recursive definition with length less than or equal to 3.
=(V, En) 5. Let n1 be an integer and define the graph Gn as follows {0,1}", the set of all binary strings of length n. Vn = Two vertices x and y are connected by an edge emu if and only if x and y differs in exactly one position. (a) (4 points) Draw the graph Gn for n = 1,2,3 (b) (4 points) For a general n 2 1, find |Vn and |En (c) (10 points) Prove that for...
2. A binary string s a finite sequence u = ala2 . . . an, where each ai įs either 0 or 1. In this case n is the length of the string v. The strings ai,aia2,...,ai...an-1,aan are all prefixes of v. On the set X of all binary strings consider the relations Ri and R2 defined as follows R, = {(u, u) | w and u have the same length } {(w, u) | w is a prefix of...
Most questions answered within 3 hours.
-
The half life of a specific Tc-99m is 6 hours. How much of an
192 mg...
asked 1 minute ago -
If you have 35.0g of Na and 100.0g of Cl2, what is the
maximum amount of...
asked 4 minutes ago -
Assume that adults have IQ scores that are normally distributed
with a mean of 96.8 and...
asked 4 minutes ago -
If a product or other segment of a business is generating a
loss, it is erroneous...
asked 7 minutes ago -
I need help writing c++ code to make this program.
1. Define a function that can...
asked 8 minutes ago -
Problem #5
A communications cable is 2.00 km long and consists of two
parallel wires separated...
asked 36 minutes ago -
Cranium, Inc., purchases term papers from an overseas supplier
under a continuous review system. The average...
asked 3 hours ago -
1- What is the freezing point of pure water (in degrees
Celsius)?
2-
he molar mass...
asked 4 hours ago -
Determine the direction of the force that will act on the charge
in each of the...
asked 4 hours ago -
You purchase your daily coffee at the Chemist’s Coffeehouse and
have a choice of two cups:...
asked 7 hours ago -
Which of the following pairs of chemicals could be used to make
a buffer solution?
A.)...
asked 7 hours ago -
Problem 16-51 Sales
Activity Variance (LO 16-3)Odessa, Inc., reports the following
information concerning operations for the...
asked 7 hours ago