Models of Computation

These are lecture notes that I wrote for the course ‘Algorithms and Models of Computation’ at the University of Illinois, Urbana-Champaign for the first time in Fall 2014. This course is a broad introduction to theoretical computer science, aimed at third-year computer science and computer engineering majors, that covers both fundamental topics in algorithms, for which I already have copious notes, and fundamental topics on formal languages and automata, for which I wrote the notes you are reading now.

These notes assume the reader has mastered the material covered in the first two years of a strong undergraduate computer science curriculum, and that they have the intellectual maturity to recognize and repair any remaining gaps in their mastery. In particular, for most students, these notes are not suitable for a first course in data structures and algorithms.

• 1 Strings
• 2 Regular Languages
• 3 Finite-State Machines
• 4 Nondeterministic Automata
• 5 Context-Free Languages
• 6 Turing Machines
• 7 Universal Models
• 8 Undecidability
• 9 Nondeterministic Turing Machines