Home, All Posts, RSS feed
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.