Course Literature
Recap on Concepts from Discrete Mathematics
- Here one can find some short notes to refresh the knowledge on basic
notions like sets, relations and functions. (The responsible of the course
would like to thank Einar Steingrímsson for these notes.)
Note: There are 2 typos in the second page on set theory; the right most B in the distributive laws (1) and (2) should be an A. - Online book on Mathematics for Computer Science by Lehman, Leighton and Meyer. Available under the terms of the Creative Commons Attribution-ShareAlike 3.0 license.
Formal Proofs, Inductive Sets, Structural Induction, Pumping Lemma
- Have a look at Koen Claessen's notes on proof
methods and structural induction.
- Ana's notes on inductive sets and induction,
and on Pumping lemma.
Main Book
Introduction to Automata Theory, Languages, and Computation, by Hopcroft, Motwani and Ullman. Addison-Wesley. Both second or third edition are fine for the course.Observe that the web page of the book contains solutions to some of the exercises in the book.
This is how some of the possible versions of the 3rd edition of the book look like:
ISBN 9780321455369 -- ISBN 9780321476173 -- ISBN 9781292039053
It seems it might be an electronic version of the book that one can buy from the publisher.
It also seems the electronic copy of the book is available for free through the library.