Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CITS2211: Assignment
This assignment has 13 questions with a total value of 66 marks. Follow the instructions on LMS for submission.
Important:
• All work is to be done individually.
• You should read carefully all instructions for this assignment in LMS.
• You do not need to write on this question sheet but do put your name and student number on every page of your
writing and do number your pages clearly in order. Your assignment will not be marked if you don’t follow these
instructions.
• Examples of how you may not get full marks for individual questions: you get the truth table but don’t complete
the proof (e.g. by not making a final statement about the final column or by not concluding the steps of inductive
proof); you don’t state the assumptions, you miss parenthesis or connectives; you don’t state the constants; you
don’t give names of steps being performed.
1
1. Imagine that a logician puts four cards on the table in front of you. On the uppermost faces, you can see E, K, 4,
and 7. He claims that if a card has a vowel on one side, then it has an even number on the other. How many cards
do you have to turn over to check this? Explain why, using reference to propositional logic. (Note this question is
slightly different from the one in Assignment 1.)
/ 2
2. Use a proof by induction to show that for any finite set S with |S| = n, where n is a nonnegative integer, then S
has 2n subsets.
/ 5
3. Prove or disprove that (A ∪B)−B = A−B for any sets A and B.
/ 5
4. Let R be a relation on the set N≥0 given by
R = {(a, b) : (b− a) is divisible by 6}
Show that this is an equivalence relation.
/ 5
5. Let X be the set {a, b, c, d, e}. Give answers to each of the following questions, justifying your answer in each case.
(a) How many functions are there which map from X to X?
(b) How many distinct total orders can be defined on X?
(c) For each function f in the set of functions from X to X, consider the relation that is the symmetric closure of
the function f . Let us call the set of these symmetric closures Y . List at least two elements of Y .
(d) Suppose R is some partial order on X. What is the smallest possible cardinality R could have? What is the
largest?
/ 8
6. For each of the following, state whether it is possible to have a function meeting the criteria given, explain why or
why not, and if it is possible, give two examples.
(a) A function f : N≥0 → N≥0 which is not surjective.
(b) A function f : N≥0 → Z which is injective.
(c) A function f : Q→ Q which is bijective.
/ 6
7. For each of the following functions, state whether it is injective, surjective, and/or bijective, and why.
(a) The function f(n) = 2n, mapping from integers to integers.
(b) The function q(ϕ), with codomain N≥0, which maps any formula of predicate logic to the number of quantifiers
in that formula.
/ 4
8. Consider the set D = {0, 1, ..., 9}∗ of all strings of digits. Define the binary relation ⪯ on D by u ⪯ v if and only if
u is a prefix of v.
For example 0061424 ⪯ 0061424535535.
Just to be clear, we also include any string as a prefix of itself.
Prove that (D,⪯) is a partial order.
/ 5
2
9. Given the following deterministic FSM M over the alphabet
Σ = {0, 1}:
s1 s2
s3
1
1
0
0
0
(a) Give an English language description of L(M), the language recognised by M.
(b) Add an error state (labelled X) to the diagram, and draw all transitions to it.
(c) Describe how to derive an FSM that accepts the complement of L(M) over the set Σ∗. (That is, an FSM that
accepts the language Σ∗ − L(M).)
(d) Give a regular expression for the complement of L(M).
/ 5
10. Convert the following regular expression into Non-Deterministic Finite Automata (NFAs), show all the steps.
(a) (0 + 1)*000(0 + 1)*
(b) (((00)*(11))+ 01)*
/ 4
11. For each of the following languages over the alphabet Σ = {a, b, c} specified by the regular expressions (a)–(c),
provide two strings in Σ∗ that are members and two strings in Σ∗ that are not members of the language (four
strings each).
(a) ab+ a
(b) ((bc)∗ + b)a
(c) (a+ ab+ abc)∗(b+ c)
/ 6
12. Assume the alphabet Σ = {0, 1}. Give three different regular expressions (besides the one given) that specify the
language described by this regular expression:
((11)∗1∗)∗ + (11 + 1)∗ + (0 + ϵ)∗
In each case, explain why your regular expression specifies the same language.
Note: For the purposes of this exercise only, changing the order of a union does not count as a different regular
expression. Your examples also should not be more complicated than the original regular expression.
/ 5
3
13. Let Σ = {0, 1} and let B be the collection of strings that contain at least one 1 in their second half. In other words,
B = {uv|u ∈ Σ∗, v ∈ Σ∗1Σ∗ and |u| ≥ |v|}
(a) Give a Push-Down Automata (PDA) that recognises B.