CS 317 Automata and Formal Languages

• Scores
• test.pl : Perl script used to test bool program

Final 10:30 Thursday.

• Instructor: Wayne O. Cochran, cochran@vancouver.wsu.edu, ELS 130Q, (360) 546-9463
• Office Hours: TBA
• Class Tuesday and Thursday, 12:00-1:15, ELS 19
  
• Textbook: Automata and Computability by Dexter C. Kozen, Springer-Verlag, © 1997, ISBN 0-387-94907-0
• Syllabus

Midterm Tues, Oct 28, 2008.

Notes

• [PDF] An unsolvable problem
• [PDF] math preliminaries
• Regular Expression Engine
  • [PDF] Building an NFA and Pattern Matching
  • NFA.java : beginning source code.
• Finding Equivalent States : from Minimization Algorithm in Lecture 14 page. 84.
• [PDF] Nondeterministic PushDown Automata NPDA
• eparse.c : pedagogical infix expression parser
• [PDF] CFL Pumping Lemma
• [PDF] Counter Machines

Assignments

1. [PDF] Math Warm Up
2. Problems 1 and 2 on page 301 (Due Thurs, Sept 11)
3. Problems 3, 4a, 5b pp 316-27 (Due Thurs, Sept 18)
4. Problems 11, 12, 13, 15, 17 pp 319- (Due Thurs, Sept 25)
5. Problem 1, p.304; Problems 14, 16, 19, 37 (use syntactically correct C programs for 37m), pp 320-; Problem 3 p.302. (Due Tues, Oct 2)
6. Problems 38, 39, 40 p. 325; 47h p. 327. (Due Thur, Oct 16)
7. [PDF] Fun with CFG's and a PDA (Due Thur, Nov 6)
8. Problems 82, 84, 85 pp.335-36 (Due Thurs, Dec 4)
9. [PDF] Boolean Logic Fun
   • Electronic submission form for problem 2b.
   • Include your name and email address and a description of how to build and run your program in a comment in your source code.
   • Make sure your program builds and runs on one of our lab machines while running Linux.
   • Hint: watch out for C's short-circuit evaluation! For example the following will not call B() if r is non-zero:

       r = r || B();