Fall 2016, University of Kentucky, Models of Computation, CS 575, with Dr Judy Goldsmith. These incomplete lecture notes are just my own, not proofread or endorsed by Dr G or UKY.
Consider the language . Is it regular, not regular but context-free, or not even context-free? (Remember that regular languages are a proper subset of context-free languages which are a proper subset of all formal languages.)
This is a finite union of simpler languages:
(Each of those is a regular expression.) A finite union of regular languages is regular, is regular and hence also context-free.
Let . Is it regular, only context-free, or neither?
Turns out that is context-free only.
Let . This is not context-free.
Let . This is context-free.
Let . This is also context-free.
And , so context free languages are not closed under intersection.
And for free we also get the languages are not closed under complement because
Union is a regular operation and intersection is not, so complement is not a regular operation.
And that’s lecture.
Public Domain Dedication.