Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CITS2211: Assignment Two 2024
This assignment has 12 questions with a total value of 60 marks. Follow the instructions on LMS for submission.
1. Draw the Hasse diagram for:
(a) The ≤ relation over the set of natural numbers (use of “...” in the diagram is allowed).
(b) The divides relation over the set of natural number divisors of 12.
(c) The “has to be put on before” relation over the set of clothes:
{right sock, left sock, left shoe, underwear, trousers, right shoe, t-shirt, coat}
/ 5
2. Let relation R over R be defined as (x, y) ∈ R iff x − y ∈ Z.
(a) Prove that R is an equivalence relation.
(b) Consider the equivalence classes generated by R
i. Is each individual class finite or infinite?
ii. Is the total number of classes finite or infinite?
/ 5
3. Consider a random person alive today and their family tree going back over the last 2000 years. By stating some sensible assumptions, prove that this family “tree” is not actually a tree as at least two of the person’s ancestors must have been the same person.
You must use reasoning that an ordinary computer scientist could quickly check without using a calculator, and only commonly known knowledge about the population of the Earth.
/ 5
4. Consider the following function π : N × N → N:
π(k1, k2) = 2/1(k1 + k2)(k1 + k2 + 1) + k2
(a) Plot a 2D graph of π with k1 on the x-axis and k2 on the y-axis, labelling the value of π(k1, k2) at each coordinate.
(b) Assume that π is a bijection and let N n = 
{ (i.e. N 1 = N, N 2 = N × N, ...). Prove rigourously that |N n | = |N| for all n ≥ 1.
/ 5
5. Consider two arbitrary (could be finite, countable, uncountable) sets A and B, and let AB be the set of all functions g : B → A. Use a diagonal argument to prove that if |A| ≥ 2 then |AB| ≠ |B|.
Hint: if there was a bijection f from B to AB, consider the value of (f(x))(x) (i.e. the output of f(x) applied to x again) for an arbitrary element x ∈ B.
/ 5
6. Consider the deterministic FSM depicted by the following diagram:
(a) Give a formal definition of this FSMs as a 5-tuple.
(b) Give an English-language description of the language recognised by the FSM.
(c) Give an equivalent regular expression for the language.
/ 5
7. Apply the power-set construction as stated in lectures to the following NFSM. Write down the result of each step, and then draw the final machine. Convince yourself that resulting DFSM accepts the same set of strings as the original NFSM (no need to write anything for this, just try a few strings out). Is there an easy, obvious way that the final result could be simplified?
/ 5
8. (a) Let Σ = {a, b}. Write regular expression for the language L consisting of all strings in Σ∗ that
i. contain exactly one occurence of the substring a
ii. contain exactly one occurence of the substring aa
iii. contain exactly one occurence of the substring aaa
(b) Simplify the following regex, explaining your reasoning
((11)∗ 1 ∗ ) ∗ + (11 + 1)∗ + (0 + ϵ) ∗
/ 5
9. Consider the following claim.
If L is a regular language then
∀ words w ∈ L where |w| > 1
∃ an expression w = xyz where
(a) ∀ i ≥ 0. xyi z ∈ L
(b) |y| ≥ 1
Is this claim true or not? If it is true, prove it. If it is false, give both an explanation and a counter-example.
/ 5
10. Design PDAs that recognises the following languages. For each automata, briefly explain in 3 sentences or less how your automata works:
(a) {a n b ma n | m, n ∈ N}
(b) {a n b m | n ≤ m ≤ 2n ∧ m, n ∈ N}
/ 5
11. Write down a context free grammar for the following languages. For each grammar, briefly explain in 3 sentences or less how your grammar works.
(a) The language of all binary strings that end with a different symbol then they start with.
(b) The language of all binary strings that contain more ones than zeroes.
/ 5
12. Suppose you have a Turing Machine M and a string x, and consider the problem “does M accept x?”. Show that this problem is undecidable by a reduction to the halting problem.
/ 5