Question

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 and v have the same length }. R2 = {(w, v) | w is a prefix of v }.

(a) Prove that R1 is an equivalence relation.

(b) Write down the equivalence classes of the strings 0, 01, and 111.

(c) Consider the set Y of all binary strings of length 2 or 3. The relation R2 on the set Y is a partial ordering. Draw a Hasse diagram of the partial order R2 on the set Y . Identify maximal and minimal elements of the poset.

Answer 1

(a)

Reflexive: let $a \in X$ . then is related to itself as length() = length(). Hence
R1
is reflexive.

Symmetric: let
al EX
and $a2 \in X$, and
R1
.

$\implies$ length() = length()

$\implies$ length() = length()

$\implies$
R1
.

Hence is symmetric.

R1

Transitive: let
al EX
and $a2 \in X$ and $a3 \in X$ , and
R1
,
R1
.

$\implies$ length() = length() and length() = length().

$\implies$ length() = length()

$\implies$
R1
.

Hence is transitive.

R1

Hence R1 is an equivalence relation.

(b)

Equivalence class of is set of all elements in related to .

Equivalence class for 0 is {0, 1}.

Equivalence class for 01 is {00, 01, 10, 11}

Equivalence class for 111 is {000, 001, 010, 011, 100, 101, 110, 111}.

(c)

The set = {00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111}.

= {(w, v) | w is a prefix of v }.

Hasse Diagram:

Maximal Elements 110111 00o 0 11 100 2101 1 01 01 01 Minimal Elements