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.)
1 answer
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