Introduction
15 questions covering all of Phase 0. Attempt everything before submitting. Each question lists the lesson to re-read if you miss it.
Practice questions
- MCQ · 1 mark
Which is TRUE?
- {∅} = ∅
- ∅ ∈ ∅
- ∅ ⊆ {∅}
- |P(∅)| = 0
- NAT · 1 mark
|P(P({a}))| = ?
Write your answer before opening the key.
- NAT · 2 marks
Number of functions from a 3-element set to a 3-element set that are NOT one-to-one?
Write your answer before opening the key.
- MCQ · 1 mark
The relation “w and v have the same length” on Σ* is:
- not reflexive
- an equivalence relation with infinitely many classes
- an equivalence relation with finitely many classes
- not transitive
- MCQ · 1 mark
The contrapositive of “if L is finite then L has a property R” is:
- If L has R then L is finite
- If L lacks R then L is infinite
- If L is infinite then L lacks R
- L is finite and lacks R
- MSQ · 2 marks
Which are valid conclusions from “P ⇒ Q” and “¬Q”?
- ¬P
- P
- Q ⇒ P
- Nothing about P
- NAT · 1 mark
A machine has 9 modes. What is the minimum input length that guarantees it visits some mode twice?
Write your answer before opening the key.
- NAT · 2 marks
Minimum number of binary strings of length 3 you must pick (repeats allowed) to guarantee picking some string at least 3 times?
Write your answer before opening the key.
- MCQ · 1 mark
In a directed graph, infinitely many distinct paths from u to v exist iff:
- v has a self-loop
- u has out-degree > 1
- some cycle lies on a path from u to v
- the graph has a cycle anywhere
- NAT · 1 mark
Number of distinct substrings (including ε) of
abba?Write your answer before opening the key.
- MCQ · 1 mark
Which has exactly one element?
- ∅
- {ε}
- Σ⁺ over {a}
- Σ¹ over {a,b}
- NAT · 2 marks
Over {a,b}, how many strings of length 7 contain at least one a AND at least one b?
Write your answer before opening the key.
- MSQ · 2 marks
Which identities hold for every language L?
- (L*)* = L*
- L∅ = ∅
- ∅* = ∅
- L*L* = L*
- NAT · 2 marks
Over {0,1}, number of strings of length 6 that start with 00 or end with 11?
Write your answer before opening the key.
- MCQ · 1 mark
Which language corresponds to “binary number divisible by 4” (no leading-zero restrictions, length ≥ 2)?
- strings ending in 00
- strings ending in 0
- strings starting with 00
- strings with four 1s
Answer key
Reveal answers when you’re ready
- C — ∅ is a subset of every set.
- A: One has an element, one doesn’t.
- B: ∅ has no elements.
- D: P(∅) = {∅} has 1 element.
- 4 — |{a}| = 1 → |P| = 2 → |P(P)| = 4.
- 21 — 3³ − 3! = 27 − 6 = 21.
- B — One class per length 0,1,2,… — infinitely many.
- A: Every string has its own length.
- C: Lengths are unbounded.
- D: Equal lengths chain.
- B — ¬R ⇒ ¬finite.
- A: Converse.
- C: Inverse.
- D: Negation of the statement.
- A — Modus tollens: ¬Q ⇒ ¬P.
- B: Contradicts the contrapositive.
- C: Converse, not implied.
- D: ¬P does follow.
- 9 — 9 symbols → 10 moments > 9 modes.
- 17 — 8 boxes; (3−1)·8 + 1 = 17.
- C — You need to be able to loop on the way.
- A: Only if v is reachable — but then it is a special case of C.
- B: Branching alone gives finitely many.
- D: A cycle elsewhere doesn’t help.
- 9 — ε; a,b; ab,bb,ba; abb,bba; abba → 1+2+3+2+1 = 9.
- B — Only ε.
- A: 0 elements.
- C: Infinite.
- D: 2 elements.
- 126 — 2⁷ − 2 (remove aaaaaaa and bbbbbbb) = 126.
- ABD — Standard identities.
- C: ∅* = {ε}.
- 28 — 16 + 16 − 4 = 28.
- A — Divisible by 4 ⇔ last two bits are 00.
- B: That is divisible by 2.
- C: Prefix doesn’t matter.
- D: Unrelated.