CS 341  Automata Theory
Elaine Rich

 

Schedule of Topics

 

Class Information:
  Textbook
  Our email addresses
  Problem sessions
  Grading
  Exams
  Policies

Website for the book

  

Errata for the book

 

Practice Exams

 

Academic Integrity

               

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:

  • Acquire a set of useful computational tools, including finite state machines, context-free grammars, and a way to identify undecidable problems,
  • Develop your intuitions about when to use each of those tools as you design and implement real applications,
  • Hone your skill at reading and writing formal logical descriptions of computational properties, and
  • Become proficient at creating formal proofs of claims about problems and programs.

 

 

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

Elaine Rich - ear@cs.utexas.edu