CSci 301 Lecture Notes

Week Four, Tuesday: Non-Context-Free Languages and Introduction to Turing Machines

The Pumping Lemma for Context-Free Languages

Theorem 2.19.

Examples 2.20, 2.21, and 2.22.

Turing Machines

A Turing machine is a model of a general purpose computer. We will see that a Turing machine can compute anything that can be computed, although other models can be much more efficient and easier to program.

Formal Definition of a Turing Machine

Definition 3.1.

Definition 3.2.

Definition 3.3.


Email: Richard dot J dot Wagner at gmail dot com

notes04a.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by Rick Wagner. Copyright © 1998-2011, all rights reserved.