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.

Guess the complexity of a language

Example 1

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.

Example 2

Let . Is it regular, only context-free, or neither?

Turns out that is context-free only.

It’s context-free because you can make a push-down automaton (a PDA) that accepts the strings and you can make a PDA that accepts the strings, and then union those two PDA’s together.

We can prove it’s not regular by using the pumping lemma. If is regular then it has a pumping length, call it . Let . Now break into three chunks (that’s concatenation) such that , . It should be possible that is in the language, but in fact it’s guaranteed that . (I thinks so, check the details yourself.) Hence, cannot be regular.

CFL’s closed under intersection?

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.