To complement the language of an NFA, the correct procedure is:

Convert to a DFA, swap there, and convert back if needed

Swap its accepting and non-accepting states

Convert to a DFA, swap there, and convert back if needed

It is impossible — NFA languages are not closed under complement

The cleanest way to prove that {aⁿbⁿ : n ≥ 0} is not regular is to observe that:

The strings a, aa, aaa, … are pairwise distinguishable, so there are infinitely many classes

No regular expression for it can be written down

The strings a, aa, aaa, … are pairwise distinguishable, so there are infinitely many classes

Two regular expressions are equivalent if and only if:

Their minimal DFAs are identical up to renaming of states

Their NFAs have the same number of states

Regular Expressions, Finite Automata and Regular Languages

Section 6 of the Computer Science paper. This is the most self-contained section in the paper: it assumes nothing from the others and its questions are almost entirely of three kinds. How many states does the minimal DFA have? Is this language regular? Are these two expressions the same language? The single most useful idea for the first is that a DFA state is a memory of exactly what still matters, and nothing else — so if a language only cares about the count of a's modulo 2 and of b's modulo 3, the minimal machine has 2 × 3 = 6 states, and if it cares which symbol sat three places back, the machine must remember the last three symbols, giving 2³ = 8. Counting states is therefore counting distinguishable situations, which is what the Myhill–Nerode theorem makes exact: the number of states in the minimal DFA equals the number of equivalence classes of strings under "which suffixes complete this into the language". That theorem is also the honest tool for the second question, since it proves a language is not regular by exhibiting infinitely many classes — and it is a cleaner instrument than the pumping lemma, which can only ever refute. The third question is settled by minimising both machines: two regular expressions are equivalent exactly when their minimal DFAs are identical up to renaming, which is a mechanical check rather than a matter of staring at the expressions. Finally, one fact worth having ready: NFAs are no more powerful than DFAs but can be exponentially smaller, and the third-from-the-end language demonstrates it — four states as an NFA, eight as a minimal DFA.

A State Is a Memory of What Still Matters

Minimal DFA sizes, each obtained by minimising the machine
Language over the given alphabet	What must be remembered	Minimal states
Binary numbers divisible by 5, read most significant bit first	The value so far, modulo 5	5
Over {a, b}: the third symbol from the END is a	The last three symbols seen	8 (= 2³)
Over {a, b}: an even number of a and a multiple of three b	Two independent counters, mod 2 and mod 3	6 (= 2 × 3)
Over {a, b}: strings of length divisible by 3	Length so far, modulo 3	3

🧠 Independent conditions multiply; the same condition does not

When a language imposes two conditions that do not interact — a count of a modulo 2 and a count of b modulo 3 — the machine has to track both, so the state count multiplies: 6, not 5. That product is the fastest way to answer most state-counting questions, and it generalises: three independent modular counters give a product of three numbers. But the rule only holds when the conditions are genuinely independent. "Divisible by 2 and divisible by 3" is a single condition in disguise, divisibility by 6, and needs 6 states rather than 2 × 3 for a reason that happens to give the same answer — while "divisible by 2 and divisible by 4" needs only 4, because the second condition subsumes the first. Checking for interaction before multiplying is the discipline.

🎯 Myhill–Nerode: why the minimal DFA is unique and how to count it

Call two strings equivalent when no suffix distinguishes them — for every z, xz and yz are either both in the language or both out. This partitions all strings into classes, and the theorem says the minimal DFA has exactly one state per class. Two consequences do the work. The minimal DFA is therefore unique up to renaming, which is what makes "are these two expressions equivalent?" a mechanical question: minimise both and compare. And a language is regular if and only if the number of classes is finite — so exhibiting infinitely many pairwise-distinguishable strings proves non-regularity directly, with no pumping and no case analysis. For {aⁿbⁿ}, the strings a, aa, aaa, … are pairwise inequivalent, since aⁱ and aʲ are separated by the suffix bⁱ. That is a complete proof in one line.

NFAs: Same Power, Exponentially Less Room

Subset construction turns any n-state NFA into a DFA of at most 2ⁿ states, so the two models recognise exactly the same languages — nondeterminism buys no power at all. What it buys is size. The language "the third symbol from the end is a" has an obvious 4-state NFA: guess that the current symbol is the one, then count two more. Its minimal DFA needs 8 states, because a deterministic machine cannot guess and must instead remember the last three symbols. Both figures here were computed, and the gap widens as 2^k for "the k-th from the end".

Closure properties: what regular languages survive
Operation	Regular languages	How you know
Union, concatenation, Kleene star	Closed	Regular expressions are built from them
Complement	Closed	Swap accepting and non-accepting states of a DFA
Intersection	Closed	Product construction, or De Morgan from the two above
Reversal, homomorphism	Closed	Reverse the NFA; relabel the transitions

⚠️ Complementing an NFA by swapping its states does not work

The swap trick is a fact about determinism, not about finite automata in general. In a DFA every string drives exactly one computation, so it either ends accepting or ends rejecting, and swapping the two sets inverts membership exactly. An NFA can have several computations on one string and accepts if any of them succeeds — so swapping the accepting set gives a machine that accepts when some path fails, which is not the complement. The correct route is to convert to a DFA first, complement there, and convert back if an NFA is wanted; the exponential cost of that first step is why complementation is cheap for DFAs and expensive for NFAs even though both recognise the regular languages. This is a favourite one-line question and the answer turns entirely on the word "any".

Key takeaways

A DFA state is a memory of exactly what still matters — count the distinguishable situations.
Independent conditions multiply: a mod 2 and b mod 3 gives 6 states, not 5.
Caring about the k-th symbol from the end costs 2^k states — 8 for the third.
Myhill–Nerode: minimal DFA states = equivalence classes, so the minimal DFA is unique up to renaming.
Infinitely many pairwise-distinguishable strings prove non-regularity in one line.
NFAs recognise exactly the regular languages but can be exponentially smaller — 4 states against 8.
Regular languages are closed under union, concatenation, star, complement, intersection and reversal.
Swapping accepting states complements a DFA and NOT an NFA, because an NFA accepts if ANY path does.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

Over the alphabet {a, b}, how many states does the minimal DFA accepting all strings whose third symbol from the end is a have?
Numerical answer — type the value.
Show answer
Answer: 8
A deterministic machine cannot know which symbol will turn out to be third from the end, so it must remember the last three symbols at all times: 2³ = 8 states, and minimisation confirms none of them merge. The same language has a 4-state NFA — guess that the current symbol is the one and count two more — which is the standard demonstration that nondeterminism buys size rather than power. The general figure is 2^k for the k-th symbol from the end, so the same question about the fifth would answer 32.
How many states does the minimal DFA accepting binary strings that represent numbers divisible by 5, read most significant bit first, have?
Numerical answer — type the value.
Show answer
Answer: 5
Five. The only thing worth remembering is the value read so far modulo 5, since reading another bit takes the running value v to 2v or 2v + 1, and that update depends on v only through its remainder. So the states are the residues 0 to 4, the start and only accepting state is 0, and minimisation shows no two residues merge. The pattern generalises immediately: divisibility by k needs exactly k states, whatever k is, which makes this a question you can answer without drawing anything.
Over {a, b}, the minimal DFA for strings with an even number of a and a number of b divisible by 3 has:
1. 5 states
2. 6 states
3. 9 states
4. 3 states
Show answer
Answer: B — 6 states
The two conditions are independent — the a-count says nothing about the b-count — so the machine must track both and the state count is the product: 2 × 3 = 6, confirmed by minimisation. Option A adds the moduli instead of multiplying, which is the commonest error. The rule is worth carrying but not blindly: it needs the conditions to be genuinely independent. "Length divisible by 2 and by 4" needs only 4 states, because the second condition already implies the first, so checking for interaction before multiplying is part of the method.
An NFA with n states is converted to an equivalent DFA. The number of DFA states is at most:
1. n
2. n²
3. 2ⁿ
4. n!
Show answer
Answer: C — 2ⁿ
2ⁿ. A DFA state in the subset construction is a set of NFA states — the set the NFA could currently be in — and there are 2ⁿ subsets of an n-element set. The bound is attained, not merely theoretical: the "third symbol from the end" language has a 4-state NFA and a minimal DFA of 8, and the k-th-from-the-end version reaches 2^k. What matters conceptually is that this is a statement about size only: both models recognise exactly the regular languages, so nondeterminism never lets an NFA accept a language no DFA can.
To complement the language of an NFA, the correct procedure is:
1. Swap its accepting and non-accepting states
2. Convert to a DFA, swap there, and convert back if needed
3. Reverse all its transitions
4. It is impossible — NFA languages are not closed under complement
Show answer
Answer: B — Convert to a DFA, swap there, and convert back if needed
The swap trick works for a DFA, where each string drives exactly one computation, so flipping the accepting set inverts membership precisely. An NFA accepts when any computation succeeds, so flipping its accepting set produces a machine that accepts when some path fails — not the complement. Hence option B: determinise first. Option D is wrong and worth being clear about: NFAs recognise exactly the regular languages, which are closed under complement — the difficulty is the cost of the construction, not its existence. That distinction between "closed under" and "cheap to compute" is the real content here.
The cleanest way to prove that {aⁿbⁿ : n ≥ 0} is not regular is to observe that:
1. No regular expression for it can be written down
2. The strings a, aa, aaa, … are pairwise distinguishable, so there are infinitely many classes
3. It is context free
4. It is infinite
Show answer
Answer: B — The strings a, aa, aaa, … are pairwise distinguishable, so there are infinitely many classes
By Myhill–Nerode, a language is regular exactly when the number of equivalence classes is finite. Here aⁱ and aʲ with i ≠ j are separated by the suffix bⁱ, which completes the first into the language and the second out of it — so every one of a, aa, aaa, … lies in a class of its own and there are infinitely many classes. One line, no case analysis. Option A is not an argument but the thing to be proved. Option C is a true statement that proves nothing, since every regular language is also context free. Option D is plainly insufficient — ab is infinite and perfectly regular.
Regular languages are closed under which of the following? (More than one may be correct.)
1. Complement
2. Intersection
3. Kleene star
4. Reversal
Show answer
Answer: A — Complement; B — Intersection; C — Kleene star; D — Reversal
All four. Union, concatenation and star come free from the definition of a regular expression; complement comes from swapping a DFA's accepting states; intersection follows either from the product construction or from De Morgan applied to the first two; and reversal from reversing every transition of an NFA and exchanging start and accepting states. This closure is unusually generous, and the reason to notice it is the contrast with context-free languages, which are closed under union, concatenation and star but not under intersection or complement. An "all of the above" answer is correct here and would be wrong for CFLs — that asymmetry is what the next chapter is built on.
Two regular expressions are equivalent if and only if:
1. They have the same length
2. Their minimal DFAs are identical up to renaming of states
3. They use the same alphabet
4. Their NFAs have the same number of states
Show answer
Answer: B — Their minimal DFAs are identical up to renaming of states
Myhill–Nerode makes the minimal DFA unique for a language, so two expressions denote the same language exactly when they minimise to the same machine. That turns equivalence from a staring contest into a decision procedure: build an NFA for each, determinise, minimise, compare. Option D fails because NFAs are not canonical — the same language has many NFAs of many sizes, and equal counts prove nothing either way. The uniqueness of the minimal DFA is also why DFA equivalence is decidable, a fact worth holding on to, because the corresponding question for context-free grammars is undecidable.