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.