Week 02 · Sipser 1.2 · Part I
Exactly two things changed from the DFA: an = became an ∈, and the input may be padded with ε. Everything below follows from those two — including the fact that determinising can cost you an exponential number of states.
eps on an arrow for an ε-move.The first row is q₀′ = E({q₀}) — the ε-closure, not just the start state. That off-by-one-row is the single commonest mistake in this construction.
Same syntax as the DFA page, plus eps for an ε-move:
q1 eps -> q2.
You cannot complement an NFA by flipping its accept states. One string can have an accepting and a rejecting computation at the same time. Try it: load an example, flip the accept set, and watch a string stay accepted. Determinise first.
Load the 2ⁿ blow-up example — an NFA for "the 4th symbol from the right is 1" with five states — and determinise it. You will get 16 states, and no smaller DFA exists: the 2⁴ strings of length 4 must all lead to different states, because for any two of them there is a suffix that one accepts and the other does not. That argument is the content of Sipser Problem 1.65, and it is the reason nondeterminism is worth having even though it adds no power.