Deterministic Finite Automata (DFA): Design, Tracing and Minimisation with Worked Examples

A DFA diagram looks simple until you must invent states, trace a long string, complement the language, or decide which states can merge. Give every state one precise meaning and preserve it through every transition. Two machines below carry that method end to end: a three-state DFA that accepts binary values divisible by 3, and a five-state machine that minimises to three.

What makes a finite automaton deterministic

A deterministic 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: Q x Sigma -> Q is a total transition function, q0 is the start state, and F is the set of accepting states.

Extend transitions to strings using delta*(q, epsilon) = q and delta*(q, xa) = delta(delta*(q, x), a). Then L(M) = {w in Sigma* | delta*(q0, w) in F}.

Determinism requires exactly one next state for every state-symbol pair. A missing transition makes the table incomplete, while two choices make the machine non-deterministic. For permanent rejection, use a dead state with self-loops.

An incoming arrow marks the start, a double circle marks acceptance, and an edge label marks an input symbol. The current state summarises relevant history. The DFA versus NFA explainer develops the wider comparison.

Worked DFA design for binary values divisible by 3

Consider L = {w in {0,1}* | value(w) mod 3 = 0}, allowing leading zeros and setting value(epsilon) = 0. States q0, q1, and q2 mean remainder 0, 1, or 2 for the prefix read. Thus Q = {q0,q1,q2}, Sigma = {0,1}, the start is q0, and F = {q0}.

Appending bit b to a prefix doubles its value and adds b, so:

new_remainder = (2r + b) mod 3

For example, (2*1+0) mod 3 = 2, so delta(q1,0) = q2. Also (2*2+1) mod 3 = 2, so delta(q2,1) = q2.

Trace 1100 from the starting configuration:

The final state accepts. Changing the last bit gives 1101: q0 -> q1 -> q0 -> q0 -> q1. Its value is 13, so it is rejected. Visiting q0 after 11 does not accept early. Only the final state matters.

How to invent states from the language condition

Ask which prefix distinctions can change the verdict after a future suffix. A state remembers exactly that information. Divisibility by 3 needs only the current remainder.

For strings ending in 01, use S for no useful suffix, A for suffix 0, and accepting B for suffix 01.

Then 1001 follows S -> S -> A -> A -> B and is accepted. Input 1010 follows S -> S -> A -> B -> A and is rejected. The transition A --0--> A is correct because, after any run of zeros, the last symbol remains the useful prefix 0.

Before drawing, test epsilon, the shortest accepted string, repeated symbols, and extensions of an accepted string. An "ends in 01" machine must leave B when needed. A "contains 01" machine instead keeps an accepting sink after the pattern appears.

Complements, products, and complete transition functions

To complement a complete DFA over a fixed alphabet, replace F with Q minus F. Keep every arrow. Completeness is the precondition, not a detail: an undefined delta(p,1) leaves p with nothing to invert on 1, so fill every missing entry first, usually with a dead state that loops on both symbols. The remainder machine already carries all 3*2 = 6 entries, and its complement within {0,1}* accepts {q1,q2} and rejects epsilon. Changing the alphabet changes the universe.

For intersection, use product states. Let E,O record even or odd numbers of 1s, and N,Z mean "empty or ends in 1" and "ends in 0". Start at EN and accept only EZ, meaning even 1s and a final 0.

Input 1010 follows EN -> ON -> OZ -> EN -> EZ and accepts. Input 110 follows EN -> ON -> EN -> EZ and also accepts. An intersection accepts pairs where both components accept, a union needs at least one, and a symmetric difference needs exactly one. Remove unreachable pairs after defining transitions.

Worked DFA minimisation from five states to three

All five states are reachable from start A; only C accepts.

Input 1001 traces A -> D -> E -> B -> C, so it is accepted, consistent with strings ending in 01.

Start refinement with P0 = {{C},{A,B,D,E}}. Under P0, both A and D send 0 and 1 to the non-accepting block. Both B and E send 0 to that block and 1 to {C}. Therefore P1 = {{C},{A,D},{B,E}}. These signatures remain distinct and stable.

The quotient DFA is:

The start is [AD]. These states behave like S, A, and B above. Two states can merge only when no future suffix distinguishes their acceptance behaviour.

Common DFA traps and their repairs

• Incomplete table: a binary DFA missing delta(p,1) is incomplete. Add the intended transition, often to a dead state that loops on both symbols.

• Prefix acceptance: 1101 visits q0 after 11 but finishes at q1, so consume the whole string before deciding.

• Wrong memory: A and D can merge, but suffix 1 distinguishes A from B: A1 is non-accepting, while B1 reaches C.

• Incorrect complement: complete the machine and fix the alphabet before swapping accepting status.

• Diagram-table mismatch: audit all |Q|*|Sigma| entries. The three-state binary remainder DFA needs 3*2 = 6 transitions in both representations.

How DFA reasoning is tested

Common problems ask you to trace strings, design states from suffix or remainder invariants, form complements or products, remove unreachable states, refine classes, or count states after minimisation. Try four checks:

1. What is delta(q2,0) in the remainder DFA?

2. Does 111 finish in an accepting state?

3. Which suffix distinguishes A from B in the five-state DFA?

4. How many states remain after minimisation?

Answers: (1) q1; (2) q0 -> q1 -> q0 -> q1, so reject because binary 111 is 7; (3) suffix 1; (4) three states, [AD], [BE], and [C].

KnowledgeGate has more than 120 DFA practice questions across basics, construction, complement, and minimisation. Use the finite automata MCQ collection for focused work. The GATE CS category is the broader route, while the GATE Test Series lists Theory of Automata in its subject-wise coverage.

The short version and next step

A DFA has exactly one next state for every state-symbol pair. Good state design stores the smallest useful summary of a prefix. Acceptance is decided after the entire string, and minimisation merges states that no suffix can distinguish.

Now rebuild the modulo-3 table from (2r+b) mod 3. Trace 10010 as q0 -> q1 -> q2 -> q1 -> q0 -> q0. Binary 10010 is decimal 18, so the original DFA accepts it and its complete complement rejects it.

For structured subject learning, continue with GATE Guidance by Sanchit Sir. After concept practice, use the GATE Test Series.