CMPU 240: Language Theory and Automata

Lectures: Tuesdays and Thursdays 3:10-4:25pm, Room 105 OLB

Office: Room 119 OLB

Phone: (845) 437-5988

Office Hours: Tuesdays and Thursdays 2-3pm and by appointment.

Syllabus Schedule Assignments CS240 Mailing List

DFA to NFA conversion in action

Course Description

This course introduces students to automata theory and formal languages, two mathmatical areas fundamental to computer science. We will consider what is an appropriate mathematical model of a computer, what types of computations are possible in the model, what types are not, the inherent complexity of certain computations, etc. Although considering computers as abstract mathematical objects may on the surface seem unrelated to "real" computing, in fact many concepts you will encounter are fundamental to important areas of computer science, including compiler design, hardware design, object-oriented design, computational linguistics, and even the syntax of the UNIX grep and awk commands.

During the course, you will gain an understanding of the intimate connection between computation and language recognition. We will study several classes of abstract machine including finite automata, push-down automata and Turing machines, along with several classes of languages such as regular and context-free languages. In addition we will look at problems like the Halting Problem that are not amenable to a computer solution.

The course provides essential background for CMPU331, Compiler Design: ideally, you should take CMPU331 in the semester immediately following completion of this course.