# Models of Computation | Lecture Notes 8

### What is this?

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:

$L = a^* \cup a^*bc \cup a^* bb cc \cup \dots \cup a^* b^5 c^5$

(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
$\overline { \overline{L_1} \cup \overline{L_2} } = L_1 \cap L_2 .$

Union is a regular operation and intersection is not, so complement is not a regular operation.

And that’s lecture.

Public Domain Dedication.