CS 451 Spring 2007: Automata and Formal Languages

CS 451 Spring 2007
Automata and Formal Languages

Department: Computer Science, U. of Alaska Fairbanks
Instructor: Glenn G. Chappell
Office: 201B Chapman
Office Hours: 2:15 M–F, or by appointment
Office phone: (474-)5736
E-mail: ffggc@uaf.edu
Paper mailbox: Inside the CS Department office, 202 Chapman

Announcements

Course Materials

Materials are listed with the most recent at the top. See below for links.

Week Class Meetings Readings & Homework Handouts, Sample Code, Etc.
Week 16 
& Finals 
5/7–5/11 
  • 5/11: Final Exam 1–3 p.m. in the classroom
  • 5/7: Other NP-Complete problems, cont’d
    
Week 15 
4/30–5/4 
  • 5/4: Restricted satisfiability, cont’d; other NP-Complete problems (10.4)
  • 5/2: An NP-Complete problem, cont’d; restricted satisfiability
  • 4/30: An NP-Complete problem, cont’d
  
Week 14 
4/23–4/27 
  • 4/27: No class (UAF SpringFest)
  • 4/25: The classes P and NP, cont’d; an NP-Complete problem (10.2)
  • 4/23: The classes P and NP, cont’d
  
Week 13 
4/9–4/13 
  • 4/20: Other undecidable problems (9.5); The classes P and NP (10.1)
    Outline: 9.5 [PDF], 10.1 [PDF]
  • 4/18: Post’s Correspondence Problem (9.4)
    Outline: 9.4 [PDF]
  • 4/16: Undecidable problems about Turing machines, cont’d
  • 4/16: Read 9.4.
  
Week 12 
4/9–4/13 
  • 4/13: An undecidable problem that is R.E., cont’d; undecidable problems about Turing machines (9.3)
    Outline: 9.3 [PDF]
  • 4/11: An undecidable problem that is R.E. (9.2)
    Outline: 9.2 [PDF]
  • 4/9: A language that is not recursively enumerable (9.1)
    Outline: 9.1 [PDF]
    
Week 11 
4/2–4/6 
  • 4/6: Turing machines & computers (8.6)
    Outline: 8.6 [PDF]
  • 4/4: Restricted Turing machines (8.5)
    Outline: 8.5 [PDF]
  • 4/2: Extensions to the basic Turing machine (8.4)
    Outline: 8.4 [PDF]
  • 4/2: Read 8.5.
Week 10 
3/26–3/30 
  • 3/30: Programming techniques for Turing machines (8.3)
    Outline: 8.3 [PDF]
  • 3/28: Turing machines, cont’d
  • 3/26: Unsolvable problems (8.1); Turing machines (8.2)
    Outline: 8.1 [PDF], 8.2 [PDF]
  • 3/30: Read 8.4.
 
Week 9 
3/19–3/23 
  • 3/23: Decision properties of CFLs, cont’d
  • 3/21: Closure properties of CFLs (7.3); decision properties of CFLs (7.4)
    Outline: 7.3 & 7.4 [PDF]
  • 3/19: Class cancelled
  • 3/19: Read 7.4.
  • 3/19: Read 7.3.
Spring Break  
Week 8 
3/5–3/9 
  • 3/9: Midterm Exam
  • 3/7: Normal forms for CFGs, cont’d; the Pumping Lemma for CFLs (7.2)
    Outline: 7.2 [PDF]
  • 3/5: Deterministic PDAs (6.4); normal forms for CFGs (7.1)
    Outline: 6.4 [PDF], 7.1 [PDF]
  
Week 7 
2/26–3/2 
  • 3/2: Equivalence of PDAs and CFGs, cont’d
  • 2/28: Equivalence of PDAs and CFGs (6.3)
    Outline: 6.3 [PDF]
  • 2/26: Definition of pushdown automata, cont’d; the languages of a PDA (6.2)
    Outline: 6.2 [PDF]
  • Assignment 5 [PDF]
    Due Mon 3/5
    Posted Wed 2/28
  • 2/28: Read: 7.1.
  • 2/26: Read: 6.3.
  
Week 6 
2/19–2/23 
  • 2/23: Ambiguity in grammars and languages (5.4); Definition of pushdown automata (6.1)
    Outline: 5.4 [PDF], 6.1 [PDF]
  • 2/21: Application of context-free grammars (5.3)
    Outline: 5.3 [PDF]
  • 2/19: Context-free grammars (5.1); parse trees (5.2)
    Outline: 5.1 & 5.2 [PDF]
  • Assignment 4 [PDF]
    Due Wed 2/28
    Posted Wed 2/21
  • 2/21: Read 5.4.
  • 2/19: Read 5.3.
Week 5 
2/12–2/16 
  • 2/16: Equivalence & minimization of automata, cont’d
  • 2/14: Decision properties of regular languages (4.3); equivalence & minimization of automata (4.4)
    Outline: 4.3 & 4.4 [PDF]
  • 2/12: Proving languages not to be regular, cont’d; closure properties of regular languages (4.2)
    Outline: 4.2 [PDF]
  • 2/16: Read 5.1.
  • Assignment 3 [PDF]
    Due Tue 2/20
    Posted Wed 2/14
  • 2/12: Read 4.4. (Yes, 4.4, not 4.3.)
Week 4 
2/5–2/9 
  • 2/9: Algebra & regular expressions (3.4); proving languages not to be regular (4.1)
    Outline: 3.4 [PDF], 4.1 [PDF]
  • 2/7: Finite automata & regular expressions (3.2)
    Outline: 3.2 [PDF]
  • 2/5: Epsilon transitions, cont’d; regular expressions (3.1)
    Outline: 3.1 [PDF]
    
Week 3 
1/29–2/2 
  • 2/2: Nondeterministic finite automata, cont’d; applications of finite automata (2.4); epsilon transitions (2.5)
    Outline: 2.4 & 2.5 [PDF]
  • 1/31: Nondeterministic finite automata, cont’d
  • 1/29: Deterministic finite automata (2.2); nondeterministic finite automata (2.3)
    Outline: 2.2 [PDF], 2.3 [PDF]
Week 2 
1/22–1/26 
  • 1/26: Concepts of automata theory (1.5); introduction to automata (2.1)
    Outline: 1.5 & 2.1 [PDF]
  • 1/24: Additional proof techniques, cont’d; inductive proofs (1.4)
    Outline: 1.4 [PDF]
  • 1/22: Additional proof techniques (1.3)
    Outline: 1.3 [PDF]
  • Assignment 1 [PDF]
    Due Wed 1/31
    Posted Wed 1/24
  • 1/26: Read 2.2.
  • 1/24: Read 1.5.
  • 1/22: Read 1.4.
Week 1 
1/16–1/19 
  • 1/19: Introduction to formal proof (1.2)
    Outline: Overview & 1.2 [PDF]
  • 1/17: Course overview
  • 1/19: Read 1.3.
  • 1/17: Read 1.1–1.2.
  • Syllabus
    Posted Fri 1/19
    Distributed in class Wed 1/17

External links last checked February 5, 2007.

Introduction to Automata Theory, Languages, and Computation
The website for our text.
Chomsky Hierarchy
An article on the Chomsky Hierarchy (of classes of phrase-structure grammars) from Wikipedia. This article is not too far from a summary of the whole of CS 451.

CS 451 Spring 2007 / Updated: 9 May 2007 / Glenn G. Chappell / ffggc@uaf.edu Valid HTML 4.01!