Computer Science 235
Languages and Automata
Fall 2015

Welcome to CS235
An introduction to the concepts of languages and automata. Topics include languages, regular expressions, finite automata, grammars, pushdown automata and Turing machines. The first half of the semester covers the Chomsky hierarchy of languages and their associated computational models. The second half of the semester focuses on decidability issues and unsolvable problems. The course includes a programming component investigating the application of automata theory to the scanning and parsing of programming languages. Course requirements will be discussed on the first day.
Prerequisite: CS230, MATH 225.
Distribution: Mathematical Modeling
Semester: Fall, Unit: 1.0

The text this semester is Automata and Computability by Dexter Kozen. The Kozen text is written as a series of lectures which may sometimes make for rough sliding in advance of the corresponding class lecture. Michael Sipser's Introduction to the Theory of Computation covers much of the same material and makes a wonderful companion text. However, it is also quite expensive and is not required for the course. If you are planning to continue in the field I would suggest acquiring both books at some point in your career. They cover foundational material that is not likely to become dated anytime soon. Copies of both books are on reserve in the Science Center Library. Additional readings will be distributed throughout the semester.

Course Materials
CS235 course materials for each class will be handed out at the beginning of each lecture. Copies are available in .pdf format using the links on this page and require the Adobe Acrobat Reader program for on-screen viewing and printing. The course resource page contains all manner of documentation for the languages and programs used in this course.

Course Conference
The course conference will contain announcements and changes to the schedule. Please check this conference before each class and especially before an assign is due. In addition, the conference will contain a section for CS235 students ask and answer questions among themselves concerning course material and assignments. You may discuss the homework in general terms, suggest where to go in the text or lecture notes to help someone get started, or you may help clarify an ambiguous question. However, please do not post your solutions either complete or partial. I will check the conference regularly to help with any unanswered questions.

Calendar of Topics and Links to Lecture Notes and Problem Sets

Randy Shull --
Based on JavaScript calendar program by Mark A. Sheldon
Computer Science 235, Fall 2015
Last Modified Oct 7
, 2015
Page Expires May 31, 2016