• Vstup: Úplný KA: M = (Q, S, R, s, F)
• Výstup: Úplný KA: M’ = (Q, S, R, s, F’),
• Metoda:
• F’ := Q – F
Algoritmus: KA pro doplněk
L(M’) = L(M)
Příklad:
a
a, b
q
s
f
b
b
a
Q – F
F
M:
F ’ = Q – F
L(M) = {x: ab je podřetězec x};  L(M ’) = {x: ab není podřetězec x}
a
a, b
f
b
b
a
M’:
s
q
15/26