Post History
#2: Post edited
by
clemens
·
2026-02-20T22:11:11Z (7 months ago)
Added information about why the question as stated in the title is the same as the question as stated in the text
- In [Worrell's lecture notes](https://www.cs.ox.ac.uk/people/james.worrell/lecture09.pdf) 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?
- In [Worrell's lecture notes](https://www.cs.ox.ac.uk/people/james.worrell/lecture09.pdf) 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: Initial revision
by
clemens
·
2026-02-20T22:08:31Z (7 months ago)
Why are regular languages closed under intersection and complementation?
In [Worrell's lecture notes](https://www.cs.ox.ac.uk/people/james.worrell/lecture09.pdf) 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?