Why are regular languages closed under intersection and complementation?
In Worrell's lecture notes I happened to find a very interesting remark:
Recall that a regular language is a language accepted by a nondeterministic finite automaton (NFA). Recall also that the class of regular languages is closed under intersection and complementation. (emphasis mine)
This fact hardly seems trivial---in fact, it came as a surprise to me since the "regexes" in computer programming (with which I'm more familiar) often don't permit the use of intersection and complementation operators.
(Note that, as any user of "regexes" knows, unions/disjunctions of regular languages are regular (this is basically because we're working with nondeterministic finite automata, hence they can "try out" all alternatives in a union/disjunction at once). So really all that's needed to answer this question is to show how complements of regular languages are regular, since intersections can be built out of unions and complements by de Morgan's laws.)
Thus, to restate my question: why, precisely, is it true that the complement of a regular language is itself a regular language?
(Again, intersections can be made out of unions and complements, so as long as the question about complements is answered, the result about intersections follows automatically.)
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| clemens | (no comment) | Mar 3, 2026 at 13:44 |
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.
0 comment threads
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| clemens | (no comment) | Mar 1, 2026 at 05:21 |
The key fact here is that regular languages are exactly the languages which can be decided by a computer with constant memory. This is basically the definition of a finite state automaton.
From here it is easy to see these facts. You've already observed this for union, but complementation and intersection are not difficult.
- Complement: A computer can recognize a regular language with constant memory, and it can negate its output with constant memory.
- Intersection: If two languages can be recognized with constant memory we can run both those programs (in parallel or serially) and take the logical and of the results. This takes at most constant+constant=constant memory.
0 comment threads
0 comment threads