Sale!

# COMP 9020 Assignment 1 solved

Original price was: \$30.00.Current price is: \$25.00.

Category:

## Description

5/5 - (1 vote)

1. (a) Compute gcd(288, 120).
(b) Compute lcm(−91, 52).
(c) What can be said about gcd(n, n + 1) for n ∈ N?
2. (a) What is card(Pow(Pow(∅)))?
(b) Show that A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C) for any sets A, B, C.
(c) Find sets A, B, C to show that A ⊕ (B ∩ C) 6= (A ⊕ B) ∩ (A ⊕ C).
3. Let Σ = {a, b}. List the elements of Σ≤3
in:
(a) Lexicographic order
(b) Lenlex order

4. (a) List all possible functions f : {a, b, c} → {0, 1}
(b) If card(A) = m and card(B) = n, how many:
(i) functions are there from A to B?
(ii) relations are there between A and B?
(c) Describe a connection between your answer for (a) and Pow({a, b, c}).

5. Let Σ = {a, b} and L = {w ∈ Σ

: 3|length(w)}. Define R ⊆ Σ
∗ × Σ
∗ as
follows: (w, w0
) ∈ R if for all v ∈ Σ

the following holds: either wv ∈ L
and w
0v ∈ L, or wv /∈ L and w
0v /∈ L. For example (a, bbb) ∈/ R because
for v = λ, av = a /∈ L but bbbv = bbb ∈ L. On the other hand, (a, b) ∈ R
because for any v ∈ Σ

, length(av) = length(bv) so av ∈ L if, and only if,
bv ∈ L.
(a) Which of the following are elements of R:
(i) (abab, baba)?
(ii) (ab, abab)?
(iii) (λ, b)?
(iv) (λ, bb)?
(v) (λ, bbb)?
(b) Show that R is an equivalence relation.
(c) How many equivalence classes does R have?
1

Advice on how to do the assignment
All submitted work must be done individually without consulting someone else’s
solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
• Assignments are to be submitted via WebCMS (or give) as a pdf
• Be careful with giving multiple or alternative answers. If you give multiple