CompSci 334, Spring 2019
Mathematical Foundations of CS

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


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.