Closure under complementation and intersection (Discrete Mathematics: Formal Languages and Automata)

I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This is the first video in a series on Formal Languages and Automata that forms the last part of the Discrete Mathematics course for first year computer scientists.

We previously defined a regular language as a formal language that is recognized by a finite automaton. We prove that regular languages are closed under complementation, that is to say: for every regular language, the language of all strings over the same alphabet that are not in that language also forms a regular language, i.e. has another finite automaton that recognizes it. I explain how to build it (easy).

Similarly, using the tools we developed in the past few videos including Kleene's theorem and the subset construction, I explain how you might in theory, given a regular expression, build another regular expression that recognized all and only the strings not recognized by the first.

We also prove that the intersection of two regular languages is a regular language, and show how to build the intersection DFA and the intersection regexp.

(Obviously regular languages are also closed under union, since union was one of the original operators we defined for regular expressions.)

Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might enjoy it.

Course web page:

Course handout:

My home page: