DFA Construction and Design: State Invariants, Worked Examples and Exam Traps

A language condition can sound perfectly clear in English, yet the state diagram goes wrong when you cannot say what each state remembers. The reliable fix is to design from state invariants, complete every transition, and trace boundary inputs. Here is that method applied to two DFAs with exact states, transitions, and results.

DFA construction starts with a precise machine and a state meaning

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 the transition function, q0 is the start state, and F is the set of accepting states.

Deterministic means every state-symbol pair has exactly one next state. Merely removing epsilon transitions is not enough. The transition function must also be total, so no pair can be missing.

A state invariant is a sentence that remains true after every processed prefix. "Seen one symbol" is vague. "The longest suffix of the processed input that is also a prefix of 101 has length 1" is testable and tells you how to update the state.

Design for the whole language, not for one sample. A path that accepts 110101 proves little unless the same machine handles every string over {0,1}, including epsilon.

Turn an English language condition into a transition table

Use this five-step routine:

1. Write the alphabet and the exact language condition.

2. Identify the minimum information that a processed prefix must retain.

3. Give every state one precise invariant.

4. Mark the start and accepting states from those invariants.

5. Fill every transition, then test epsilon, a shortest accepted string, a near miss, repeated symbols, and a longer accepted string.

Treat each transition as an invariant update. For every state and symbol, ask: after appending this symbol, which invariant is now true? Build a table before drawing the graph because a blank or duplicated edge is easier to spot in a table.

A rejecting sink is required only when no later suffix can repair a violation. An accepting sink is correct for a permanent fact such as "has already contained 101". It is wrong for a temporary fact such as "currently ends in 101", which a later symbol can change.

Worked DFA construction for binary strings containing 101

Let L1 = {w in {0,1}* | w contains 101 as a substring}. The machine needs four levels of matched-prefix progress:

• q0: no useful suffix matches a prefix of 101

• q1: the longest useful suffix is 1

• q2: the longest useful suffix is 10

• q3: 101 has occurred

The start state is q0, and F = {q3}.

Two fallbacks deserve attention. From q1, another 1 keeps the machine in q1 because the new 1 can begin a fresh occurrence of 101. From q2, a 0 produces suffix 100, which has no non-empty suffix that is a prefix of 101, so the machine returns to q0.

For 110101, the complete trace is q0 --1--> q1 --1--> q1 --0--> q2 --1--> q3 --0--> q3 --1--> q3. It finishes in q3, so it is accepted.

For 111000, the trace is q0 --1--> q1 --1--> q1 --1--> q1 --0--> q2 --0--> q0 --0--> q0. It finishes in q0, so it is rejected.

Prove the DFA with invariants, not selected examples alone

After any processed prefix, q0, q1, and q2 record the longest suffix matching a prefix of 101, with lengths 0, 1, and 2. State q3 records the permanent fact that the complete pattern has appeared. Every table entry preserves this claim, so finishing in q3 is equivalent to belonging to L1.

Boundary traces provide a useful error check. epsilon, 0, 1, 10, and 1001 all finish outside q3. The strings 101, 0101, 1010, and 110101 finish in q3. These tests can expose a bad edge, while the invariant argument covers every possible input.

Do not confuse "contains 101" with "ends in 101". For the contains language, both outgoing edges from q3 return to q3 because later input cannot erase an earlier occurrence. An ends-with machine must keep updating suffix progress and can leave its accepting state.

Product-state DFA for even 1s and an ending 0

Now let L2 = {w in {0,1}* | w has an even number of 1s and ends in 0}. Two independent memory bits are needed: parity E/O, and last-symbol flag N/Z. Here, N means the input is empty or ends in 1, while Z means it ends in 0.

Their product gives four states. EN is the start state, EZ is the only accepting state, and ON and OZ are rejecting.

Input 1 flips parity and makes the last-symbol flag N. Input 0 preserves parity and makes the flag Z.

Trace 1010 as EN --1--> ON --0--> OZ --1--> EN --0--> EZ. It is accepted because it contains two 1s and ends in 0. Trace 100 as EN --1--> ON --0--> OZ --0--> OZ. It is rejected because it contains one 1, even though it ends in 0.

DFA design traps and how to repair them

• Drawing states from a sample input. A longer or overlapping input then has no consistent interpretation. Write one reusable invariant sentence per state before drawing edges.

• Leaving an edge blank or giving it two destinations. Then delta is not a total function, so the machine is not a DFA. Make a |Q| x |Sigma| table and fill every cell exactly once.

• Resetting q1 on the second 1. This loses the useful final 1 in 11. Compute the longest useful suffix after each symbol.

• Making q3 leave its accepting region. That treats a contains condition like an ends-with condition and wrongly rejects longer strings such as 1010. Decide whether acceptance is permanent.

• Accepting when either product component is true. That would accept 100 just because it ends in 0. For an intersection, accept only when both component conditions hold, which means only EZ here.

If direct construction is clear but the starting object is already nondeterministic, NFA to DFA Conversion for GATE explains reachable-subset construction. Once a complete DFA exists, DFA Minimization for GATE: Minimum States, Step by Step addresses which states can be merged. Neither procedure replaces defining the correct state memory during direct design.

DFA construction in exams: question types and the next step

Common tasks ask you to translate a language into a table, select the correct diagram, trace a string, repair a wrong edge, combine conditions with product states, or decide whether states can later be merged. KnowledgeGate has about 70 published DFA Construction & Design questions, so use several forms of the same idea instead of memorising one diagram.

The short version is five lines:

1. Define the language and alphabet.

2. State exactly what each state remembers.

3. Fill every state-symbol transition.

4. Mark acceptance from the invariant.

5. Trace boundary inputs and justify every result.

Use CS Fundamentals for Exams & Placements to place DFA design in the wider subject sequence. For structured syllabus coverage, follow GATE Guidance by Sanchit Sir. After rebuilding both DFAs from memory, use the GATE Test Series for timed practice.