Comp 285 - Home Page

Comp 285 - Theory of Computation

Spring 2007

Instructor: Brian Shelburne 329E Science
Office: 329E Science
Class times: MWF : 10:20 - 11:20 Rm 327 Science

Text : An Introduction to Formal Languages and Automata, 3rd Ed.; P. Linz
JFLAP An Interactive Formal Languages and Automata Package, S. Rodgers & T. Finney

This course deals with the problem of what is means to "compute". We will look at languages, grammars, and automata and the relations between the three. Theory of Computation is one of the oldest "areas" in computer science (many results were established before the first stored program computers became operational) and provides the theoretical underpinning for the discipline. It has many applications to other areas of computer science like programming techniques, programming languages, compiler design, algorithms, and defining computational complexity (i.e. defining what a "hard" problems is).

Subjects Covered in this Course

Finite State Automata, Regular Languages, Regular Grammars and their properties
Push Down Automata, Context Free Languages, Context Free Grammars and their properties
Turing Machines and Unlimited Grammar

Reading Assignments : Reading assignments with suggested homework problems will be assigned the class period before the material is covered in class. Therefore it is expected that the student will have some familiarity with the lecture material. A Theory of Computation course is very much like a course in mathematics in that you will need to keep up with the reading assignments so as not to get behind and you will need to do the daily homework problems.

The Context Free Parser Programming Project : The study of grammars (one of the topics covered in the course) leads very naturally into compiler construction. The only high-level language programming assignment for this course will involve writing both a top-down and bottom-up parser that accepts an accepts an arbitrary context free grammar and tests if any arbitrary string is a member of the language generated by the grammar.

Links to Class Notes

JFLAP - The Java Formal Language and Automata Package is located at

Q:\Computer:\Computer Science\Classes\Comp285\JFLAP

Simply click on jflap.jar or RunJFLAP.bat OR you can download your own free copy by going to http:\\www.jflap.org
A Turing Machine Program : Information about the MS-DOS based Turing Machine simulator used in this course. Includes a link to a zip file containing an executable version of the simulator.
A Non-Deterministic Push Down Antomaton Program: A zip file containing an executable version of an npda simulator and a pdf file with information on how to use it.
The Church-Turing Thesis : Entry from Stanford University's Encyclopedia of Philosophy on the Church-Turing thesis.
A Finite State Automaton Program: From Webworks at Montana State University in Bozeman, this Java applet allows the user to create and run FSA's. A nice graphical interface. Click here to load the applet directly. Be patient - it takes time to load! Read the instructions while waiting.

Return to Alternate Home Page