States and the DFA

1. What is the difference between ∅ and {ε}?
   Stuck? Peek at 0.3.2 Σᵏ, Σ*, Σ⁺ and languages

   • |Σᵏ| = |Σ|ᵏ; Σ⁰ = {ε}; Σ* = ⋃ Σᵏ (k ≥ 0); Σ⁺ = Σ* − {ε}.
   • #strings of length ≤ n over k symbols = (kⁿ⁺¹ − 1)/(k − 1); binary: 2ⁿ⁺¹ − 1.
   • Language = any subset of Σ*. ∅ (no strings) ≠ {ε} (one string). Exactly r of one symbol in length n (binary): C(n, r).
   • Shortlex order lists every string at a finite position.

   Read lesson 0.3.2

2. How many functions are there from a 6-element set to a 3-element set?
   Stuck? Peek at 0.2.2 Functions, relations and equivalence classes

   • Relation ⊆ A × B. Function: every input exactly one output. Partial function: some inputs have none.
   • #functions A→B = |B|^|A|. #one-to-one (|A| ≤ |B|) = |B|·(|B|−1)···. #relations on n-set = 2^(n²).
   • Equivalence = reflexive + symmetric + transitive. Classes partition the set; number of classes = index.
   • Finer relation (refinement) ⇒ more classes; every fine class sits inside a coarse class.

   Read lesson 0.2.2

3. A machine with 4 modes reads 4 symbols. Must it repeat a mode?
   Stuck? Peek at 0.2.4 Pigeonhole principle

   • n + 1 objects in n boxes ⇒ some box has ≥ 2.
   • N objects in k boxes ⇒ some box has ≥ ⌈N/k⌉. To force m in a box: (m−1)k + 1 objects.
   • Machine with n modes, input length ≥ n ⇒ some mode repeats ⇒ a loop in the input.

   Read lesson 0.2.4

Back to the even/odd machine from Lesson 0.1.1. It had two modes, EVEN and ODD, and a rule for every (mode, symbol) pair. It read the input once, left to right, never went back, never wrote anything down — and still answered correctly for inputs of any length.

That is exactly how the text-search inside your editor, the lexer inside a compiler, and the controller inside a lift work. They are all the same mathematical object: a Deterministic Finite Automaton (DFA). This lesson gives the modes their real name — states — and writes the machine down so precisely that there is no room for doubt.

Over Σ = {a, b}, a machine must accept exactly the strings that start with a. It must have a rule for every state and every symbol. How many states do you think it needs?

Prediction check

Answer: 3. One state for “nothing read yet” (the start), one for “first symbol was a — accept whatever follows”, and one for “first symbol was b — reject whatever follows”. That third one is a dead state: once you enter it you can never leave and never accept. Most people guess 2 because they forget it.

States

A state is a mode of a finite-memory machine: a summary of everything the machine needs to remember about the input read so far. The machine has a fixed, finite set of them, chosen before any input arrives.

The formal definition (5-tuple)

“Deterministic” means δ is a (total) function: for every state and every symbol there is exactly one next state. No choices, no missing rules.

How a DFA runs

1. Start in q₀, with the head before the first symbol.
2. Read one symbol a, move from the current state q to δ(q, a).
3. Repeat until the input is used up.
4. If the final state is in F, accept; otherwise reject.

A DFA always finishes: one step per symbol, so an input of length n takes exactly n steps. It never loops forever and never gets stuck.

Two ways to draw δ

Transition diagram: a labelled directed graph (Lesson 0.2.5). Nodes = states; an arrow labelled a from p to q means δ(p, a) = q; an arrow from nowhere marks q₀; a double circle marks an accepting state.

Transition table: one row per state, one column per symbol, entry = next state. Mark the start row with → and accepting rows with *.

The dead (trap) state

A dead state is a non-accepting state whose every transition loops back to itself. Once entered, the input is rejected no matter what follows. It exists because δ must be total: when a string is already hopeless, the DFA still needs somewhere to go.

Many diagrams leave the dead state out to reduce clutter (any missing arrow means “go to the dead state”). That is only a drawing shortcut; the real DFA still has it.

Counting DFAs

With n states, alphabet size m, and a fixed start state: δ has n·m entries, each one of n states → nⁿᵐ choices; F is any subset → 2ⁿ choices. Total nⁿᵐ · 2ⁿ DFAs (multiply by n if the start state may also vary).

Putting it together

• A DFA is (Q, Σ, δ, q₀, F) with exactly one move per (state, symbol); it reads each symbol once and always halts.
• It accepts iff it ends in F; it accepts ε iff q₀ ∈ F.
• Missing arrows mean a dead state, and minimal-DFA counts include it.

The even-a’s DFA and the starts-with-a DFA are live below. Press Step to watch the highlighted state move; try the example chips.

Transition table — even number of a's          trace of "baba"
        a    b                                 E ─b→ E ─a→ O ─b→ O ─a→ E   end E ∈ F → ACCEPT
→*E     O    E                                 trace of "ab"
  O     E    O                                 E ─a→ O ─b→ O               end O ∉ F → REJECT

Transition table — starts with a
        a    b
→ q0    q1   D        trace "ab":  q0 ─a→ q1 ─b→ q1   ACCEPT
* q1    q1   q1       trace "ba":  q0 ─b→ D ─a→ D     REJECT (trapped)
  D     D    D        trace "ε":   stays q0 ∉ F       REJECT

States are Lesson 0.1.1’s modes; δ is a function of two inputs (0.2.2); the diagram is a labelled directed graph (0.2.5). Next lesson: what exactly is the set of strings a DFA accepts, and how do we follow a whole string through δ at once?

1. MCQ

   In a DFA M = (Q, Σ, δ, q₀, F), δ is a function from:

   1. Q → Σ
   2. Q × Σ → Q
   3. Q × Σ → P(Q)
   4. Σ → Q
2. NAT

   Minimum number of states of a DFA over {a,b} accepting exactly the strings that start with ab?

   Write your answer before opening the key.

3. MSQ

   Which are true for every DFA?

   1. It halts after exactly |w| steps on input w
   2. It accepts ε iff its start state is accepting
   3. It may have two transitions on the same symbol from one state
   4. Its number of states is finite
4. NAT

   How many DFAs have 3 states {p, q, r}, alphabet {0}, and start state p?

   Write your answer before opening the key.

5. MCQ

   A dead state is:

   1. an accepting state with self-loops
   2. a non-accepting state from which no accepting state is reachable
   3. the start state
   4. a state with no incoming arrows

• state
• DFA (Q, Σ, δ, q₀, F)
• transition function δ
• start state q₀
• accepting / final state, F
• transition diagram
• transition table
• dead / trap state
• deterministic (exactly one move)

1. 5-tuple of a DFA?
   Reveal answer

   (Q, Σ, δ, q₀, F): states, alphabet, transition function Q×Σ→Q, start state, accepting states.
2. When does a DFA accept ε?
   Reveal answer

   Exactly when q₀ ∈ F.
3. Does GATE count the dead state in “minimal DFA” questions?
   Reveal answer

   Yes, whenever the language needs one.
4. States needed for a DFA accepting exactly one string of length k?
   Reveal answer

   k + 2 (k+1 progress states + dead).
5. Number of DFAs with n states, m symbols, fixed start?
   Reveal answer

   nⁿᵐ · 2ⁿ

• Quick dead-state check: is there a prefix after which no continuation can be accepted? If yes, the minimal DFA has a dead state — count it.