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.

Example: Prove a language’s complexity

Let $L = \{ a^n b^m a^n : n, m \geq 0 \}$. This language is context-free and
not regular.

Proof that $L$ is context-free

It’s context-free because there exists a grammar that generates exactly $L$:

Proof that $L$ is not regular

We will use the pumping lemma for regular languages.

Suppose $L$ were regular. Then it has some sufficent pumping length $p$.

Let $w = a^p b^p a^p$. There should exist some way to split $w$ into three
pieces, $w = xyz$, so that three conditions hold:

$xy \leq p$

$y > 0$

$\forall i \geq 0: x y^i z \in L$

Note that $w$ has three chunks; chunk 1 is $a$’s, chunk 2 is $b$’s, and chunk 3
is $a$’s again.

No matter how we split up $w$, $y$ must be completely within the first two
chunks. Then in the string $s’ = x y^5 z$, the first chunk and the third chunk
are different sizes. So $s’ \notin L$.

So there exists a sufficently long string in $L$ that cannot possibly be pumped,
so $L$ cannot be regular.

Minimizing duress on the final

Some of us were pretty panicked during the midterm. You are allowed to bring a
stuffed animal or anything like that to the final if it will help you not
panic. Dr G does not want you to panic.

Introducing the Turing Machine

The Turing Machine has something that nothing else so far has had. A read/write
tape.

A RW tape is like a stack where you can slide up and down it without
destroying it.

Remember that a language is called regular if there is a DFA that recognizes
it, and called context-free if there is a PDA that recognizes it. We call a
language computable if there is a Turing machine that recognizes it.

Some languages that are not context-free are computable, e.g.
$L = \{ a^n b^n c^n : n \geq 0 \}$.