FA for Complement: Problem
• Previous algorithm requires a complete FA
• If M is incomplete FA, then M must be converted to
  a complete FA before we use the previous algorithm
a
s
f
b
c
Incomplete DFA:
c
a,b
qfalse
a,b,c
Complete DFA:
b
a
s
f
c
M:
Example:
c
a,b
a,b,c
a
c
f
s
b
qfalse
M2’:
L(M2’) = L(M)
L(M1’) ¹ L(M)! - c Ï L(M), c Ï L(M1’)
s
c
a
f
b
M1’:
16/26