• Input: Incomplete DFA M = (Q, S, R, s, F)
• Output: Complete DFA Mc = (Qc, S, Rc, s, F)
• Method:
• Qc := Q È {qfalse};
• Rc := R È {qa ® qfalse: a Î S, q Î Qc,   qa ® p Ï R,  p Î Q}.
Algorithm: DFA to Complete DFA
 Gist: Add a “trap” state
33/44