Exercises

• #1 - Induction is your friend! (Answer Key)
• #2 - Diagonalization is definitely NOT your friend! (Answer Key)
• #3 - DFAs and NFAs (Answer Key)
• #4 - Regular Expressions (Answer Key)
• #5 - Context-Free Languages and Grammars (Answer Key)
• #6 - Turing Machines (Answer Key)

Course Slides

Disclaimer: Note that the following slides will be changed througout the semester, and students are responsible for any such changes occurring prior to an associated exam.

• Course Overview
• Background - Induction, relations, diagnalization, etc.
• Introduction to Languages
• Regular Languages, DFAs and NFAs
• Regular Expressions
• Properties of Regular Languages
• Context-Free Languages and Context-Free Grammars
• Pushdown Automata
• Properties of Context-Free Languages
• Showing a Language is Not Context-Free #1(pdf only!)
• Showing a Language is Not Context-Free #2(pdf only!)
• Turing Machines
• Closure Properties

Course Videos

• Test Video

Helpful Links

• Finite Automata Drawing Utility
• Context-Free Grammar Developer Tool
• The Book's Website (Introduction to Automata Theory, Languages, and Computation)
• Jeff Ullman's Automata Theory Course Videos
• Lego Turing Machine
• Boring Turing Machine
• The Halting Problem Explained