Post History

> Recall that a regular language is a language accepted by a nondeterministic finite automaton (NFA)

This is true, and for some purposes it's the most useful perspective, but there's an alternative perspective which is more useful for proving this type of property. A regular language is a language accepted by a **deterministic** finite automaton (DFA). The two claims are equivalent. Obviously every DFA is an NFA. Slightly less obviously, every NFA can be converted to a DFA at risk of an exponential blowup in the number of states: the states of the DFA are the powerset of the states of the NFA.

The advantage of the DFA perspective is that regularity of complementation drops out immediately: just complement the set of accepting states. Intersection is also easily demonstrated by forming a new DFA whose states are the Cartesian product of the states of the two DFAs to be intersected.