COMP 455: Models of Languages and Computation

• Instructor: Nathan Otterness
• Time: Monday and Wednesday, 9:05 - 10:20 AM
• Location: FB 007
• Syllabus: comp455_s19_syllabus.pdf

Class Slides

0. Introduction
1. Preliminaries
2. Finite Automata
   • Animation on Slide 5: DFA
   • Extra slides: Additional Proof Examples from Class
   • Animation on Slide 32: NFA
   • Animation on Slides 50-53: NFA with Epsilon-Transisions
3. Regular Expressions
4. Properties of Regular Languages
5. Context-Free Grammars
6. Pushdown Automata
   • Animation on Slide 3: Simplified PDA
7. Properties of Context-Free Languages
   • Animation on Slide 54: PDA Inverse Homomorphism Operation
   • Extra slides: Second example and more explanation for the CYK algorithm.
8. Turing Machines
   • Animation on Slide 11: Turing Machine Execution
   • Animation on Slide 45: Turing Machine Shifting Symbols Over
9. Undecidability
10. NP Completeness

Miscellaneous Notes

• A great online tool for drawing automata (useful if you're typing your homework): Finite State Machine Designer. (I modified this version from the original to automatically crop images.)