When one input symbol activates two destinations, the NFA is in both states. Treating nondeterminism as a set-valued transition removes the guesswork. For L = {w in {0,1}* | the second symbol from the right in w is 1}, one three-state machine supports direct design, positive and negative traces, boundary tests, and reachable-subset conversion.
Set-valued transitions and the NFA acceptance test
A nondeterministic finite automaton is a five-tuple M = (Q, Sigma, delta, q0, F). Here, Q is a finite set of states, Sigma is the input alphabet, delta is the transition function, q0 is the start state, and F is the set of accepting states.
For an ordinary NFA, delta: Q x Sigma -> 2^Q. The notation 2^Q means that a transition returns a set of possible next states, which may contain zero, one, or several states. A DFA instead has exactly one next state for every state-symbol pair. Nondeterminism is a mathematical branching model, not random guessing or a claim about parallel hardware.
After the whole input is consumed, the NFA accepts exactly when the current state set intersects F. The Finite Automata: DFA vs NFA Explained comparison shows how a set-valued transition differs from a DFA, while CS Fundamentals organises the surrounding subject.
Worked NFA design for a second-last 1
Consider the language L = {w in {0,1}* | the second symbol from the right in w is 1}. Build the machine directly from that sentence.
State q0 scans any prefix. Whenever it reads 1, the NFA may remain in q0, or guess that this 1 is the second-last symbol and enter q1. State q1 must consume exactly one final symbol and move to accepting state q2. State q2 has no outgoing transition, because a guess that reaches it before the input ends must fail.
The complete NFA has Q = {q0,q1,q2}, Sigma = {0,1}, start state q0, and F = {q2}.
State | Input | Input |
|---|---|---|
|
|
|
|
|
|
| empty set | empty set |
Boundary checks matter. Strings of length zero or one have no second-last symbol, so they reject. Among length-two strings, 10 and 11 accept because their second-last symbol is 1; 00 and 01 reject.
Trace accepted and rejected strings as state sets
Never select one branch and discard the others. For 1010, begin with S0 = {q0} and apply each symbol to every active state.
Consumed prefix | Active state set |
|---|---|
|
|
|
|
|
|
|
|
|
|
The branch guessed after the first 1 reaches q2 after 10, then dies on the next 1. The later branch created after the third symbol reaches q2 when the input ends. Since S4 = {q0,q2} contains q2, 1010 accepts.
Now trace 1001 in the same way.
Consumed prefix | Active state set |
|---|---|
|
|
|
|
|
|
|
|
|
|
The final set does not contain q2, so 1001 rejects. This agrees with the language statement because its second-last symbol is 0.
Epsilon-closure extends the same state-set method
An ordinary NFA and an epsilon-NFA are related but distinct. An epsilon-NFA may move without consuming input, so its transition type is delta: Q x (Sigma union {epsilon}) -> 2^Q. Take the relevant epsilon-closure before reading the first real symbol and after every move. A closure includes its starting states and every state reachable through any number of epsilon moves.
Consider states {s,a,b,f}, alphabet {0,1}, start state s, accepting set {f}, and transitions s -epsilon-> a, s -epsilon-> b, a -0-> f, and b -1-> f. All unspecified transitions are empty.
First, epsilon-closure({s}) = {s,a,b}. On input 1, move({s,a,b},1) = {f}, and then epsilon-closure({f}) = {f}. Therefore 1 accepts. The empty string rejects because the initial closure {s,a,b} does not contain f. Epsilon changes the state set, but it is not an input symbol.
Reachable subsets for the second-last-1 machine
Subset construction turns each reachable NFA state set into one DFA state. For the three-state NFA above, name the reachable subsets A = {q0}, B = {q0,q1}, C = {q0,q2}, and D = {q0,q1,q2}. Start at A.
DFA state | NFA subset | Input | Input |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Only C and D accept, because they contain the NFA accepting state q2. Re-running 1010 gives A -> B -> C -> B -> C, which ends accepting. Re-running 1001 gives A -> B -> C -> A -> B, which ends rejecting.
The DFA and NFA recognise the same language even though they represent state differently. Minimisation comes only after construction, as explained in DFA Minimization for GATE. No two of A, B, C, and D can be merged merely because their labels look similar; minimisation requires an equivalence proof.
Four checks that expose a broken NFA design
Choosing one next state:
delta(q0,1) = {q0,q1}means both states become active. Carry both until a transition kills a branch or the input finishes.Accepting too early: acceptance is checked after all input is consumed. In
1010, one branch reachesq2after10but dies on the next symbol.Treating a missing arrow as a loop: a missing transition means the empty set. Every branch at
q2dies if more input remains.Mixing definitions: an NFA does not necessarily have fewer states than every equivalent DFA. State counts depend on the language and construction. Epsilon transitions belong specifically to epsilon-NFAs.
Before trusting a design, test the shortest accepted string, a just-too-short string, a clear positive, and a near-miss negative. For this machine, 10, 1, 1010, and 1001 fill those four roles.
Use the worked machine as an exam checklist
Stable question forms include identifying a diagram's language, computing the active set after a prefix, deciding whether a string is accepted, constructing an NFA from a language condition, and converting an NFA or epsilon-NFA into a DFA. Subset construction applies in both cases, with epsilon-closure added where needed.
Try four rapid checks on the worked machine: epsilon rejects; 11 accepts; after prefix 101, the active set is {q0,q1}; and the accepting DFA subsets are C and D. Justify each answer from the transition table rather than pattern matching.
After concept work, the GATE Test Series provides timed practice through topic-wise tests and mocks. Use it to check whether the state-set method still holds when diagrams and language conditions change.
A reusable verification routine and the next study step
Translate the language sentence into one job per state. Write every transition as a set, carry the full active set after each symbol, and accept only when the final set intersects F. For an epsilon-NFA, take epsilon-closure before the first symbol and after each move.
Next, redesign the main machine for “the third symbol from the right is 1” by adding one countdown state. Trace one accepted and one rejected input. For broader Computer Science concept learning, continue with the Zero to Hero Complete CS Course.
