### 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 7.1 . 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

- First class is January 21, 2021.

### Homeworks/Projects

The required work in this course includes in-class group work, online
quizzes on the reading,
homework consisting of written assignments and JFLAP
assignments, and
one three-part programming assignment (an interpretor for a new programming
language).

### Required Background:

CompSci 201 and CompSci 230 or equivalent. Talk to Prof. Rodger if you
have not taken CompSci 230.