KA pro doplněk: Problém
• Předchozí algoritmus vyžaduje úplný KA
• Pokud M není úplný KA, potom M musí být převed na úplný KA a pak může být použit předchozí algoritmus
a
s
f
b
c
Neúplný DKA:
c
a,b
qfalse
a,b,c
Úplný DKA:
b
a
s
f
c
M:
Příklad:
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