Definition: Let M = (Q, S, R, s, F) be a DFA. M is complete, if for any p Î Q, a Î S there is exactly one rule of the form pa ® q Î R for some q Î Q; otherwise, M is incomplete
S = {a, b, c}
a
s
f
b
c
Conversion: Incomplete DFA
?
a
b
c
?
?
c
a, b
qfalse
a, b, c
to Complete DFA
b
a
s
f
c
Complete DFA
32/44
Gist: Complete DFA cannot get stuck.