Proof:
Theorem:
The family of regular languages is
closed under
complement
.
Closure properties: Complement
•
Let
L
be a
regular language
•
Then, there exists a complete DFA
M
:
L
(
M
) =
L
•
We can construct a complete DFA
M
’
:
L
(
M
’
) =
L
by using the previous algorithm
•
Every
FA defines a regular language, so
L
is a
regular language
17/26