• Input: Complete FA: M = (Q, S, R, s, F)
• Output: Complete FA: M’ = (Q, S, R, s, F’),
• Method:
• F’ := Q – F
Algorithm: FA for Complement
L(M’) = L(M)
Example:
a
a, b
q
s
f
b
b
a
Q – F
F
M:
F ’ = Q – F
L(M) = {x: ab is a substring of x};  L(M ’) = {x: ab is no substring of x}
a
a, b
f
b
b
a
M’:
s
q
15/26