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.