Formal Languages and Automata, Fall 1999

MW 7:00--8:15pm

Most of these are available in either postscript (*.ps) or adobe acrobat (*.pdf) form.

Handouts

• Syllabus (ps) / (pdf) / (html)
• A Universal Function for S (ps) / (pdf)
• Smn and KRT (ps) / (pdf)
• The Rice-Shapiro Theorem (ps) / (pdf)
• Turing Machine Construction Techniques (ps) / (pdf)
• Turing Machines and Computability (ps) / (pdf)
• Basic FLT Refresher Tutorial

  • Part 1 (through Induction) (ps) / (pdf)

    • Solutions to Part 1 (ps) / (pdf)

  • Part 2 Finite and Regular Languages

    • Finite Languages through DFAs (ps) / (pdf)

      • Solutions (ps) / (pdf)

    • NFAs through Equivalence of Regular and Recognizable Languages (ps) / (pdf)

      • Solutions (ps) / (pdf)

    • Pumping Lemma through Decision Problems) (ps) / (pdf)

      • Solutions (ps) / (pdf)

  • Part 3 Context-Free Languages

    • Phrase-Structure Grammars to Parsing (ps) / (pdf)

      (Target date 25/Oct)

      • Solutions (ps) / (pdf)

• FLT Review Test (Due 3 Nov.) (ps) / (pdf) / (html)

Assignments

• Assignment 1 (ps) / (pdf) / (html)
• Assignment 2 (ps) / (pdf)
• Assignment 3 (ps) / (pdf)
• Assignment 4 (ps) / (pdf)
• Assignment 5 (ps) / (pdf)

Solutions

• Assignment 1 (ps) / (pdf)
• Assignment 2 (ps) / (pdf)
• Assignment 3 (ps) / (pdf)
• Assignment 4 (ps) / (pdf)
• Assignment 5 (ps) / (pdf)