Computer Science 235
Languages and Automata
Fall 2007

Instructor
Lyn Turbak
SCI E126, x3049
Office Hours:

  • Monday 4-6pm
  • Tuesday 1-2:30pm
  • Wednesday 4-6pm
  • Friday 3-5pm
  • and by appointment

Course Description
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. Prerequisite: 230, MATH 225.
Distribution: Mathematical Modeling
Semester: Fall, Unit: 1.0

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. This program is installed on most public computers at Wellesley College. If your computer does not have a working copy of Acrobat Reader, it is available for free from Adobe on all major computer platforms. Click on the button to the left to download Acrobat Reader. Note that there are plug-ins that allow you to read .pdf files directly from your browser; again, these are installed on most public computers and are freely available from Adobe.

Course Conference
The course conference, CS235-F07, contains two subconferences:

  • CS235-F07 Announcements will be used to announce schedule changes, corrections/clarifications for problem sets, and other messages of general interest. Please check this conference before each lecture and especially before a problem set is due.
  • CS235-F07 Q&A will be used to answer student questions about course material. Please review this when working on your problem sets to see if a question you have has already been answered. Students may answer questions from other students. 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 any part of your solutions!

Textbooks

This semester, we will be using many resources from Alley Stoughton's Forlan Project for teaching formal language theory. Most of our readings will be from Stoughton's textbook:

An Introduction to Formal Language Theory That Integrates Experimentation and Proof

You may also find it helpful to study Stoughton's slides for his book and materials for his CIS 570 Introduction to Formal Language Theory course at Kansas State University.

Certain topics for this semester are not covered in Stoughton's book. So there will also be readings (some required, most optional) from the textbooks below. You needn't buy these books since the number of required readings from them is small and there are copies of these books in SCI 173. Ping Lyn if you have trouble finding them.

Course Schedule
Below is a tentative schedule for the lectures. Lecture slide handouts are linked from each lecture.

Part 1: Foundations

Part 2: Regular Languages

  • Lec. 07 (Wed. Sep. 19) Yet More SML; Formal Languages
    Lecture 7 slides
    Reading: Stoughton 2.1 -- 2.2
  • Lec. 08 (Thu. Sep. 20) Regular Expressions
    Lecture 8 Slides
    Reading: Stoughton 3.1
    Optional Reading: Kozen 9; first part of Sipser 1.3
  • Lec. 09 (Mon. Sep. 24) More Regular Expressions
    (no new slides)
  • Lec. 10 (Wed. Sep. 26) Equivalence and Simplification of Regular Expressions
    Lecture 10 slides
    Reading: Stoughton 3.2
  • Lec. 11 (Thu. Sep. 27) More Regular Expression Simplification; Forlan
    (no new slides)
    Reading: Stoughton 2.3
    Problem Set 1 Solutions
  • Lec. 12 (Mon. Oct. 1) Finite Automata and Labeled Paths; Checking Acceptance and Finding Acceptance Paths
    Lecture 12 slides
    Reading: Stoughton 3.3, 3.5, 3.6
    Problem Set 2 Due
  • Lec. 13 (Wed. Oct. 3) Converting Between Regular Expressions and Finite Automata
    Lecture 13/14 slides
    Reading: First part of Stoughton 3.11
  • Lec. 14 (Thu. Oct. 4) More Conversion
    Lecture 13/14 slides
    Problem Set 3 Out (due Mon. Oct. 15 ((extended to Wed. Oct. 17)))
  • Fall Break (Sat. Oct. 6 -- Tue. Oct. 9)
  • Lec. 15 (Wed. Oct. 10) Specialized Automata: EFAs, NFAs, and DFAs
    Lecture 15 slides
    Reading: Stoughton 3.8, 3.9, 3.10, relevant parts of 3.11
    Optional Reading: Kozen 5 and 6; Sipser 1.2
  • Lec. 16 (Thu. Oct. 11) Operations on DFAs: Complement, Intersection, Difference, and Equivalence
    Lecture 16 slides
    Reading: Stoughton 3.10, 3.12
    Optional Reading: Kozen 3, 4, 13 and 14, Sipser 1.1
  • Lec. 17 (Mon. Oct 15) DFA Operations Continued; DFA Minimization
    Lecture 17 slides
    Reading: Stoughton 3.12
  • Lec. 18 (Wed. Oct 17) Midterm Review
    Problem Set 3 Due
    Problem Set 2 Solutions
  • Lec. 19 (Thu. Oct 18) In-class Midterm
  • Lec. 20 (Mon. Oct 22) Regular Language Applications: String Searching, Pattern Matching, and an Introduction to Lexical Analysis
    Lecture 20/21 slides
    Reading: Stoughton 3.14; Appel Chapters 1 and 2
  • Lec. 21 (Wed. Oct 24) Lexical Analysis Continued
    Reading: User Manual for ML-Lex
  • Lec. 22 (Thu. Oct 25) The Pumping Lemma: A Technique for Proving that Languages are Nonregular
    Lecture 22 slides
    Reading: Stoughton 3.12; Sipser 1.4
    Problem Set 4 Out (due Mon. Nov. 5 (extended to Thu. Nov. 15)) Kitty Reference Manual

Part 3: Context-Free Languages

  • Lec. 23 (Mon. Oct 29) Pumping Lemma Continued; Context-Free Grammars: A Way to Specify Some Nonregular Languages
    Lecture 23/24 slides
    Reading: Stoughton 4.1; first part of Sipser 2.1
  • Lec. 24 (Wed. Oct 31) Context-Free Grammars Continued
  • Lec. 25 (Thu. Nov. 1) Ambiguous Grammars
    Lecture 25 slides
    Reading: Stoughton 4.6
  • Lec. 26 (Mon. Nov. 5) Specialized Grammars: Linear Grammars and Chomsky Normal Form
    Lecture 26 slides
    Reading: Stoughton 4.4, 4.8, and 4.9; last part of Sipser 2.1
    Optional Reading: Kozen 21
  • Lec. 27 (Wed. Nov. 7) Pushdown Automata: Machines for Context-Free Languages
    Lecture 27/28 slides
    Reading: Sipser 2.2
    Optional Reading: Kozen 23
  • Lec. 28 (Thu. Nov. 8) Pushdown Automata Continued
  • Lec. 29 (Mon. Nov. 12) Properties of Context-Free Languages: A Pumping Lemma for CFL and CFL Closure Properties
    Lecture 29 slides
    Reading: Stoughton 4.7 and 4.10; Sipser 2.3
  • Lec. 30 (Wed. Nov. 14) Pumping and CFL Closure Properties Continued; Introduction to Parsing
    Lecture 30/31 slides
    Reading: Stoughton 4.3
  • Lec. 31 (Thu. Nov. 15) Introduction to Parsing Continued
    Problem Set 4 Due
  • Lec. 32 (Mon. Nov. 19) Predictive Parsing
    Lecture 32/33 slides
    Reading: Appel 3.2
  • Thanksgiving Break (Wed. Nov. 21 -- Sun Nov. 25)

Part 4: Computability

  • Lec. 33 (Mon. Nov. 26)Predictive Parsing Continued
    Problem Set 5 Out (due Tue. Dec. 4 (extended to Thu. Dec. 6))
  • Lec. 34 (Wed. Nov. 28) Shift-Reduce Parsing: Procrastination is Good
    Lecture 34/35 slides
    Reading: Appel 3.3
  • Lec. 35 (Thu. Nov. 29) Shift-Reduce Parsing Continued; ML-YACC
    Reading: Appel 3.4, User Manual for ML-Yacc
  • Lec. 36 (Mon. Dec. 3) The Church-Turing Thesis: Turing Machines and Effective Computability
    Lecture 36 slides
    Reading: Sipser Chapter 3
    Optional Reading: Kozen 28, 29, 30; Stoughton 5.1
  • Lec. 37 (Wed. Dec. 5) Decidable and Undecidable Languages
    Lecture 37/38 slides
    Reading: Sipser 4, 5.1, 5.3
    Optional Reading: Stoughton 5.2 -- 5.3; Kozen 32 and 33
  • Lec. 38 (Thu. Dec. 6) Decidable and Undecidable Languages (continued)
    Problem Set 5 Due
  • Lec. 39 (Mon. Dec. 10) Rice's Theorem Meets Program Analysis
    Lecture 39 slides
    Reading: Kozen 34
  • Final Exam Period (Fri. Dec. 14 -- Thu. Dec. 20)
    Self-Scheduled Open Book/Notes Final Exam

Problem Sets

Other Handouts

Documentation/Resources