B2 · Finite automata, recalled

Where you are in the story

Phase 2 gives regular languages three more faces (expressions, grammars, closure rules) and finally proves where they stop. Every conversion in Phase 2 starts or ends at a DFA or NFA, so refresh them now.

Previous phase in pictures

A DFA, running

Ends with 01

States: q0, q1, q2

Transitions: q0>q0: 1; q0>q1: 0; q1>q1: 0; q1>q2: 1; q2>q0: 1; q2>q1: 0

Ends with 01: three states, one move per symbol, accept if the run ends in a double circle. Step through the examples.

DFA design patterns at a glance

Language (\|w\| = k)	Minimal states
starts with w	k + 2
contains w / ends with w	k + 1
length ≡ r (mod n)	n
#a mod m and #b mod n	m·n
binary ÷ k, k = 2ʲ·m (m odd)	m + j
k-th symbol from the start	k + 2
k-th symbol from the end	2ᵏ

The highlighted row is the NFA story: tiny NFA, exponential DFA.

NFA → DFA: sets of states

Subset construction: each DFA state is one corner of this cube.

Minimization: merge states with the same future

parts illustration

Myhill–Nerode: futures decide everything

finitely many futures

regular; #classes = #states of the minimal DFA

infinitely many futures

not regular — e.g. aⁱ separated by bⁱ in aⁿbⁿ

Carry these forward

DFA 5-tuple?

(Q, Σ, δ, q₀, F) with δ : Q × Σ → Q total. (1.1.1)

Does GATE count the dead state?

Yes, in minimal-DFA questions whenever the language needs one. (1.1.1)

When is L(M) infinite?

When a cycle lies on a path from q₀ to an accepting state. (1.1.2)

Starts-with vs contains (|w| = k)?

k + 2 vs k + 1. (1.1.3)

Product construction for L₁ ∩ L₂?

Pairs of states; accept F₁ × F₂; ≤ m·n states. (1.1.4)

How to complement a DFA?

Complete it (dead state), then swap accepting and non-accepting. Not for NFAs. (1.1.4)

When does an NFA accept?

If at least one path ends in an accepting state. (1.2.1)

What is ECLOSE(q)?

States reachable by ε-moves only, including q. (1.2.2)

NFA with n states → DFA states?

At most 2ⁿ; k-th from end needs 2ᵏ. (1.2.3)

First step of minimization?

Remove unreachable states, then split {F, Q−F}. (1.3.1)

Exactly / at least / at most k a’s?

k+2 / k+1 / k+2 states. (1.3.2)

Myhill–Nerode theorem?

Regular ⇔ finitely many classes; classes = minimal states. (1.3.3)

Moore vs Mealy output length?

n + 1 vs n. (1.4)

Quick refresher

NAT
Minimal DFA states over {a,b}: strings that contain abb?
Write your answer before opening the key.
NAT
Minimal DFA states: 3rd symbol from the end is a, over {a,b}?
Write your answer before opening the key.
MCQ
Swapping accepting states of an NFA gives:
1. always the complement
2. not necessarily the complement
3. the reversal
4. the empty language
NAT
Minimal DFA states for binary numbers divisible by 12?
Write your answer before opening the key.
MSQ
Which languages are not regular?
1. {aⁿbⁿ}
2. strings with #a = #b
3. strings with #a even
4. strings ending in ab

What the next phase adds

DFA / NFA

machines that check

regular expressions

formulas that describe

regular grammars

rules that generate

limits

pumping lemma: what no DFA can do

Phase 2: the same family of languages, seen three new ways — and its boundary.

Answer Vault

Reveal answers when you’re ready

4 — k + 1.
8 — 2³.
B — Several paths per string break it.
- A: Only for complete DFAs.
- C: Unrelated.
- D: Unrelated.
5 — 12 = 2²·3 → 3 + 2.
AB — Infinitely many Myhill–Nerode classes.
- C: 2 states.
- D: 3 states.