Models of Computation | Lecture Notes 9

2016 October 10. Monday.

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.

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$ :

$S \to aSa | T$

$T \to bT | \epsilon$

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 \}$ .

Public Domain Dedication.