Non-Deterministic Finite Automata (NFA): Design, Epsilon Closures and NFA-to-DFA Conversion

An NFA can be in several possible states after one input prefix. That feels like guesswork until you remember the acceptance rule: only one complete path needs to finish in a final state. Tracking the whole set of active states turns that rule into ordinary bookkeeping. The four-state NFA below, for the language whose third symbol from the right is 1, reaches exactly eight distinct active sets, and those eight sets are the states of an equivalent DFA.

What makes a finite automaton non-deterministic

An NFA without epsilon moves is N = (Q, Sigma, delta, q0, F), where delta: Q x Sigma -> P(Q). Its transition function returns a set, unlike a DFA transition function, which returns exactly one state. Thus delta(q,a) may contain no state, one state, or several states. A missing NFA transition need not be drawn as an explicit dead state.

For w = a1a2...ak, acceptance means that at least one path starts at q0, consumes all k symbols in order, and ends in F. To simulate all paths together, take S0 = {q0} and compute each Si as the union of delta(q,ai) over every q in S(i-1). Accept exactly when Sk intersects F.

This is mathematical branching, not randomness. The machine gives the same answer every time. See Finite Automata: DFA vs NFA and Subset Construction for the side-by-side comparison and a smaller three-state conversion.

Worked NFA design: the third symbol from the right is 1

Consider L = {w in {0,1}* | |w| >= 3 and the third symbol from the right is 1}. Use start state q0, checkpoints q1 and q2, and final state q3:

The loop at q0 scans any prefix. On a 1, a second branch may enter q1, guessing that this symbol is third from the end. Exactly two more symbols carry it through q2 to q3. Extra input kills that branch because q3 has no outgoing transition, but a later guess may survive.

Trace 10110:

{q0} -> {q0,q1} -> {q0,q2} -> {q0,q1,q3} -> {q0,q1,q2} -> {q0,q2,q3}

The final set contains q3, so accept. For 10010:

{q0} -> {q0,q1} -> {q0,q2} -> {q0,q3} -> {q0,q1} -> {q0,q2}

The earlier visit to q3 is not enough because input remained. The final set excludes q3, so reject.

Epsilon-NFAs and the epsilon-closure routine

An epsilon-NFA uses delta: Q x (Sigma union {epsilon}) -> P(Q). An epsilon edge changes state without consuming a character. The epsilon-closure(S) contains S itself and every state reachable from it through zero or more epsilon moves.

For L = 0* union 1*, make non-final start s, add s --epsilon--> a and s --epsilon--> b, make a and b final, give a only a 0 loop and b only a 1 loop. The start closure is {s,a,b}, so epsilon is accepted. The traces are:

• 000: {s,a,b} -> {a} -> {a} -> {a}

• 111: {s,a,b} -> {b} -> {b} -> {b}

• 001: {s,a,b} -> {a} -> {a} -> empty, so reject

Always apply S0 = epsilon-closure({s}), then Si = epsilon-closure(move(S(i-1),x)). Epsilon moves can be eliminated and do not create languages beyond the regular languages.

Convert the worked NFA to a DFA by subset construction

Each DFA state is one reachable NFA active set:

The starred subsets are accepting. For example, delta_DFA(C,1) = delta(q0,1) union delta(q2,1) = {q0,q1} union {q3} = F. Also, delta_DFA(D,0) = {q0} union {q2} union {q3} = G.

The DFA gives 10110: A -> B -> C -> F -> D -> G, so it accepts. It gives 10010: A -> B -> C -> E -> B -> C, so it rejects. Audit every row with one rule: the DFA subset must equal the active NFA set after the same prefix.

Why NFAs help even though DFAs recognise the same languages

Every DFA is already an NFA with one destination per transition. In the other direction, subset construction converts every NFA or epsilon-NFA to a DFA. The saving is countable here: the NFA above needs four states, while the smallest DFA for the same language needs eight, because a DFA has to remember the last three symbols outright. Both machines still recognise exactly the regular languages.

An n-state NFA has at most 2^n subsets, including empty. Here, 2^4 = 16, but only the eight listed subsets are reachable. Empty is unreachable because q0 survives every prefix. If empty is reached in another conversion, it becomes a DFA dead state with a loop on every symbol.

NFAs also make operations neat. To unite machines for strings ending in 00 and strings ending in 11, add a new start with epsilon edges to both old starts. For concatenation, add epsilon edges from the first machine's final states to the second start. For star, add a new accepting start and epsilon routes for zero or further repetitions. None of this lets an NFA recognise {0^n1^n | n >= 0}.

Common NFA traps and how to repair them

• All paths: one complete accepting path is enough. In {q0,q2,q3}, non-final states do not cancel q3.

• Early final: reaching q3 after prefix 100 does not accept 10010. Attach an input position to each set.

• Epsilon: an epsilon edge consumes no symbol. Include the initial closure, {s,a,b} here.

• Subsets: {q0,q2} equals {q2,q0}. Canonicalise sets, remove unreachable ones, and mark a subset final if any member is final.

• Diagram mismatch: the NFA relation has two destinations from q0 on 1; the eight-state DFA function has 8 * 2 = 16 transition cells.

How GATE-style questions test NFA reasoning

Common tasks ask you to find an active set, evaluate an epsilon closure, design for a suffix condition, determinise an NFA, identify final subsets, count reachable subsets, or compare languages. Test yourself:

1. What is delta(q0,1) above?

2. Which active set follows 101?

3. What is the epsilon-NFA start closure?

4. Where does DFA state C go on 1?

5. How many subsets are possible and reachable here?

Key: {q0,q1}; {q0,q1,q3}, which accepts 101; {s,a,b}; accepting F={q0,q1,q3}; 16 possible and 8 reachable.

KnowledgeGate has more than 90 Non-Deterministic FA practice questions across NFA design, epsilon conversion, NFA-to-DFA conversion, and regularity identification. Use the Finite Automata MCQ collection for focused practice, and the GATE CS category as a broader preparation route.

Short version and next step

An NFA transition returns a set, one complete accepting path is sufficient, epsilon closure adds states without consuming input, and subset construction makes each reachable set one DFA state. NFAs can be more compact than DFAs, not more expressive.

Now rebuild the four-state machine for "the third symbol from the right is 1". Check 01000:

{q0} -> {q0} -> {q0,q1} -> {q0,q2} -> {q0,q3} -> {q0}

It rejects because the final set excludes q3. The DFA trace A -> A -> B -> C -> E -> A confirms it.

For structured subject-wise learning, continue with GATE Guidance by Sanchit Sir. Use the GATE Test Series later for mock-based mixed practice.