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. PrenticeHall, 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
