CS 341 Automata Theory
Elaine Rich
|
Class
Information: |
|
In
this class, we will develop a single framework in which all kinds of
computational problems can be defined and analyzed. The framework is
based on the idea of a language, and problems are defined as the task of
determining whether an input string is a member of some particular
language. Thus this area is often called formal language theory.
But a key idea is that all problems can be described as language
recognition tasks so this framework shouldn’t be thought of as
limiting. Instead, think of it as a simple mechanism by which problems
that may initially appear very different can be compared and analyzed to see
whether there can exist computational solutions to them at all, and, if there
can, what power those solutions must possess. We will discuss
computational models ranging from very simple (finite state machines) to
pushdown automata (with the power to recognize context free languages,
including standard programming languages) to Turing Machines, which are
powerful enough to solve any problem for which a solution exists, yet simple
enough to describe that we can prove theorems about what they can and cannot
do. In this
class, you will:
Texts I have
written a text book for this class, Automata,
Computability and Complexity: Theory and Applications. Prentice-Hall, 2008. It should be available at the Coop or
online from Amazon or Barnes and Noble. There is a website that
goes along with the book. It is
organized into pages that correspond to the chapters of the book. On those pages, you will find links to many other useful sites. If you would like another
book as a supplementary text, I recommend Introduction to the Theory of
Computation, Michael Sipser. Brooks/Cole, 1996. Contact Information
|