### Course Description:

An introduction to theoretical computer science including studies
of abstract machines, the language hierarchy from regular languages
to recursively enumerable languages, noncomputability and complexity
theory.

This course explores the foundations of how compilers work and explores
this theory with hands on experience of the concepts using the software
JFLAP . With JFLAP one can experiment with structures and proofs, such as
programming finite state machines and Turing machines, or to show that a
finite state machine is equivalent to a regular expression. Suppose you are
asked to create a new programming language for a specific device. How would
you write a compiler or interpretor for such a language?
One would first identify the
individual words in a program (lexical analysis) and then check to see if
those words form a valid program (syntax analysis). We will explore several
parsing techniques such as LALR and write an interpretor for a simple
language.

### Course Announcements

- Class starts January 9, 2014.

### Homeworks/Projects

The required work in this course includes in-class group work,
and homework consisting of written assignments, JFLAP
assignments and one three-part programming assignment.

### Required Background:

CompSci 201 and CompSci 230 or equivalent. Talk to Prof. Rodger if you
have not taken CompSci 230. (Note: we are in the process of changing the math
prereq for this course to CompSci 230 which is a better fit).