The Nature of Computation only glancingly treats automata, languages, and grammars because we wanted to focus on more modern aspects of computational complexity. But we understand that many introductory courses include them. If you want to include them feel free to use Cris' lecture notes on automata,languages, and grammars.

Courses that are or have been using The Nature of Computation, either as the main text or as recommended reading: CSC2401S: Introduction to Computational Complexity Stephen A. Cook, University of Toronto COMP-252: Honours data structures and algorithms Patrick Hayden, McGill CS190: The Nature of Computation Wim van Dam, UCSB Automata, Computability, and Complexity Scott Aaronson, MIT Philosophy of Computation Walter Dean, U. Warwick Algorismia Josep Diaz, Universitat Politecnica de Catalunya Barcelona Theory of Computation Tom Hayes, UNM Theoretical Computer Science Bernard Moret, EPFL Stochastic Processes: Random and Quasirandom Simulation James Propp, U. Mass Lowell Markov Chain Monte Carlo Algorithms Dana Randall, Georgia Tech. Introduction to Theory of Computing Alex Russell, U. Connecticut Theory of Computation Denis Thérien, McGill Introduction to Natural Computing Manish K Gupta, Dhirubhai Ambani Institute of Information and Communication Technology (India) A Theorist's Toolkit Ryan O'Donnell, Carnegie Mellon Theory of Computation Matt Franklin, UC Davis Theory of Computation Otfried Cheong, KAIST (Korea Advanced Institute of Science and Technology) CS 125: Algorithms and Complexity Michael Mitzenmacher and Salil Vadhan, Harvard Heuristic Problem Solving Bud Mishra, NYU Advanced Theory of Computation Denis Thérien, McGill ECS 220: Theory of Computation Matt Franklin, UC Davis IT-468: Introduction to Natural Computing Manish K. Gupta, DA-IICT (India) Please drop us a note if you are using our book for your course.