exercise 1.14

a. Theorem

Show that if M is a DFA that recognizes language B, swapping the accept and nonaccept states in M yields a new DFA recognizing the complement of B. Conclude that the class of regular languages is closed under complement.

a. Proof

This proof is based on induction.

Base case: a DFA with a single state, don't care what is the alphabet. Every letter brings to the only state. Obviously, if the state is an accepted state (F = {q0}), the DFA accepts every string; if the state is a non-accepted state (F = ∅), the DFA doesn't accept strings.

Inductive step: Let N a DFA that respect the theorem. If we add a new state Fnew, we must add an outgoing arrow for each letter and we can add some incoming arrow, moving them from other states.

Now, there are three cases: if the string ends before reaching Fnew, the theorem is proven, because the existence of Fnew isn't relevant. If the string ends at Fnew, the change of the acceptance of Fnew inverts the behavior of the DFA.

If the string ends at the state after Fnew, that we can name Fnew+1, the change of the acceptance of Fnew+1 inverts the behavior of the DFA.

After Fnew+1, we are again inside N, so the theorem is proved.

a. Proof (2)

For each string s, the membership of each state at F don't change the path that s follows. So, if s ends in an accepted state, the string is accepted, and changing this state the string isn't accepted anymore; and vice versa.

a. Conclusion

Let S a class of strings s composed by letters of Σ. Each string of s must belong to a regular language recognized by N or ¬N, since every state is accepted in N or ¬N.

Since "A language is called regular language if some finite automaton recognizes it" (Sipser, definition 1.16), all the languages that recognize every string s must be recognized by N or ¬N.

b. Theorem

Show by giving an example that if M is an NFA that recognizes language C, swapping the accept and nonaccept states in M doesn’t necessarily yield a new NFA that recognizes the complement of C. Is the class of languages recognized by NFAs closed under complement? Explain your answer.

b. Proof

A simple example is:

N = ({q0, q1}, {A, B}, δ, q0, {q0, q1})
δ = (q0, A) = q1

the string "B" is not recognized both by N and ¬N

Since every NFA have an equivalent DFA (Sipser, theorem 1.39), and the NFA is a special class of DFAs, the class of NFA is closed under complement.