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.
Let . This language is context-free and not regular.
It’s context-free because there exists a grammar that generates exactly :
We will use the pumping lemma for regular languages.
Suppose were regular. Then it has some sufficent pumping length .
Let . There should exist some way to split into three pieces, , so that three conditions hold:
Note that has three chunks; chunk 1 is ’s, chunk 2 is ’s, and chunk 3 is ’s again.
No matter how we split up , must be completely within the first two chunks. Then in the string , the first chunk and the third chunk are different sizes. So .
So there exists a sufficently long string in that cannot possibly be pumped, so cannot be regular.
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.
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. .
Public Domain Dedication.