B1 · Foundations, recalled

Where you are in the story

Phase 0 gave you the vocabulary. Phase 1 uses every piece of it at once: modes become states, rules become a function, diagrams are labelled graphs, and what a machine accepts is a language. Spend ten minutes here so none of it feels foreign.

Previous phase in pictures

Sets: regions you can shade

Union, intersection, difference, complement — Phase 1 builds machines for each of these.

Equivalence classes: infinitely many things, finitely many groups

parts illustration

Pigeonhole: long inputs force loops

ABCBArepeat ⇒ loop

A machine with n modes reading n or more symbols repeats a mode.

Graphs: the shape of every machine diagram

Directed graph with labelled edges

States: 0, 1, 2, 3, 4

Transitions: 0>1: a; 1>2: b; 2>2: c; 2>3: b; 3>1: d; 0>4: e

Labelled one-way edges; paths spell words; infinitely many paths need a cycle on the way.

Strings and languages

Σ* all strings

a language L any subset

{ε} one string: the empty one

∅ no strings

The universe for every complement from now on is Σ*.

Carry these forward

|P(A)| when |A| = n?

2ⁿ — one in/out switch per element. (0.2.1)

A − B in terms of ∩ and complement?

A ∩ B̅. (0.2.1)

Number of functions from A to B?

|B|^|A|. (0.2.2)

Three properties of an equivalence relation?

Reflexive, symmetric, transitive. Its classes partition the set. (0.2.2)

Which statement is equivalent to P ⇒ Q?

The contrapositive ¬Q ⇒ ¬P. (0.2.3)

n-mode machine, input length m: when must a mode repeat?

When m ≥ n (m + 1 moments). (0.2.4)

When are there infinitely many paths from u to v?

When a cycle lies on a route between them. (0.2.5)

Number of prefixes of a length-n string?

n + 1, including ε and the string itself. (0.3.1)

∅ vs {ε}?

0 strings vs 1 string (the empty one). (0.3.2)

∅* = ?

{ε}. And L∅ = ∅. (0.3.3)

What does “machine M accepts L” mean?

M says yes on every string in L and on no string outside L. (0.3.4)

Quick refresher

NAT
|P({a, b, c, d})| = ?
Write your answer before opening the key.
MCQ
Which is equivalent to “if the machine has 2 modes, it cannot count to 3”?
1. If it cannot count to 3, it has 2 modes
2. If it can count to 3, it does not have 2 modes
3. If it does not have 2 modes, it can count to 3
4. It has 2 modes and can count to 3
NAT
Over {0,1}, how many strings have length at most 3?
Write your answer before opening the key.
MSQ
Which equal {ε}?
1. ∅*
2. {ε}*
3. ∅
4. Σ⁰
NAT
An equivalence relation on strings groups them by length mod 4. Its index?
Write your answer before opening the key.

What the next phase adds

modes

Phase 0 word

states

Phase 1 word

rules

“in this mode, on this symbol, go there”

δ : Q × Σ → Q

a function of two inputs

drawing

arrows between modes

transition diagram

a labelled directed graph

what it says yes to

L(M), a language

regular when a DFA exists

Every Phase 1 idea is a Phase 0 idea with a new name.

Answer Vault

Reveal answers when you’re ready

16 — 2⁴.
B — Contrapositive.
- A: Converse.
- C: Inverse.
- D: The negation.
15 — 1 + 2 + 4 + 8.
ABD — Star always yields ε; Σ⁰ is the set of length-0 strings.
- C: ∅ has no strings.
4 — Remainders 0–3.