Welcome to Comp 116.

Catalog Descritpion: Many complex problems can be solved using a finite state machine approach. This course is a look at various kinds of such theoretical machines and how understanding them can lead to practical solutions to programming problems. Topics include regular languages, context-free languages, finite automata, pushdown automata, nondeterminism and Turing machines. The halting problem and the problem of computability versus undecidability are investigated. The topics are shown to have applications to compiler design; portions of a compiler are implemented in a major project.

Course Basics

Lecture:

Mon-Wed 2:00PM-3:20PM, Science Center 1313

Instructor:	Martin Gagné
Email:	lastname_firstname at wheatoncollege dot edu
Office:	Science Center 1323
Drop in Hours:	Monday 3:30PM-4:30PM Tuesday 10:30AM-12:00PM Thursday 2:30PM-4:00PM and by appointment
Tutors:	TBA

Course Textbook

The following is probably the most frequently used book to teach this course, and I will follow it pretty closely:

• Introduction to the Theory of Computation, by Michael Sipser.

The book is available at the bookstore, where it is outrageously overpriced. You can also get it on Amazon, where it is a little better, but still pretty pricey. Quite frankly, I would recommend that you just use the eBook version you can access from the library (login needed). It's a couple editions behind, but it has everything we need, and I will cover everything in class anyway, so worst case, you can probably manage without the book completely if needed.