DFA design

DFA design is the craft of going from a description of a language ('strings that contain 11', 'numbers divisible by 3', 'an even count of a-s') to an actual machine that recognises it. The single guiding question is wonderfully concrete: as I scan the input left to right, what is the minimum I must remember to know later whether to accept? Each distinct answer to that question becomes a state.

A reliable recipe. First, name the facts you must track and make one state per distinct relevant situation — for 'divisible by k' track the running remainder mod k (k states); for 'even number of a-s' track a single parity bit (2 states); for 'contains the substring 011' track how much of 011 you have matched so far (states for matched 0, 01, and a done-and-accepting state). Second, decide the start state (what is true of the empty input). Third, fill in δ: for each state and each symbol, ask which fact-situation you land in next. Fourth, mark the accept states (which situations mean success). Finally, make δ total — add a trap state for any 'this has failed' route.

Two more design tools. The product construction lets you combine two conditions ('even number of a-s AND ends in b') by running two machines side by side: states are pairs, one component per condition. And throughout, resist storing more than you need — if a property only depends on a bounded fact, a finite set of states suffices; if it secretly needs an unbounded count, no DFA exists and you should suspect the language is not regular.