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 $L = \{ a^i b^j c^j : 0 \leq i, 0 \leq j \leq 5 \}$.
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, $L$ is regular and hence also context-free.

Example 2

Let $L = \{ a^j b^k c^m : j > k \textrm{ or } k \not= m \}$. Is it regular, only
context-free, or neither?

Turns out that $L$ is context-free only.

It’s context-free because you can make a push-down automaton (a PDA)
that accepts the $j > k$ strings and you can make a PDA that accepts the
$k \not= m$ strings, and then union those two PDA’s together.

We can prove it’s not regular by using the pumping lemma. If $L$ is
regular then it has a pumping length, call it $p$. Let $s = a^{p+1} b^p c^p$.
Now break $s$ into three chunks $xyz = s$ (that’s concatenation) such that
$|xy| \leq p$, $|y| > 0$. It should be possible that $x y^0 z$ is in the
language, but in fact it’s guaranteed that $x y^0 z \notin L$. (I thinks so,
check the details yourself.) Hence, $L$ cannot be regular.

CFL’s closed under intersection?

Let $L = \{ a^n b^n c^n : n \geq 0 \}$. This is not context-free.

Let $L_1 = \{ a^n b^n c^k : n, k \geq 0 \}$. This is context-free.

Let $L_2 = \{ a^n b^k c^k : n, k \geq 0 \}$. This is also context-free.

And $L_1 \cap L_2 = L$, 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.