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
q
false
a
,
b
,
c
Complete DFA:
b
a
s
f
c
M
:
Example:
c
a
,
b
a
,
b
,
c
a
c
f
s
b
q
false
M
2
’
:
L
(
M
2
’
)
=
L
(
M
)
L
(
M
1
’
)
¹
L
(
M
)
!
-
c
Ï
L
(
M
),
c
Ï
L
(
M
1
’)
s
c
a
f
b
M
1
’
:
16/26