We covered deterministic and nondeterministic finite state machines in class on 24 September (see NotesSeptember24). This material is included in WrittenAssignment2. Class on 28 September and 1 October covered regular expressions and the pumping lemma (presumably included in NotesSeptember28 and NotesOctober1); that material will be included in the first exam but is not on the problem set.
Readings from Course Texts
The following texts are available in the library and have been purchased by students in this class. Almost any theory of computation book will cover this material, but the chapter numbers presumably won't match. You are also welcome to use other resources -- including those web resources listed below -- instead or as supplement. Please let us know (e.g., by wiki-fying your comments) if you find something particularly helpful!
- Hopcroft, Motwani, Ullman 2e: Chapter 2 + Sections 3.1, 3.2 + Section 4.1. The remainder of chapters 3 and 4 are interesting but not required.
- Lewis and Papadimitriou 2e: Chapter 2
- Sipser: Chapter 1
Note that each of these books contains an introductory chapter that covers the mathematical notation and foundations used later in the book. (Interesting puzzle: How does Sipser manage this when FSMs are chapter 1?)
Online resources
This list is not as well triaged as it might be, so please feel free to add comments or rearrange as you find things (un)helpful.
JFLAP tool we used in class to simulate FSM operation
- Note that these are xml text files that can be loaded into JFLAP, but they're not much good otherwise
Automata Definitions, seemed mathy on first reading, but I think this is the best link of the bunch - K
CS2490 Lecture Notes Some chapters are skimpy, but most seem to be useful intros/reinforcements to material.
Finite State Machines, okay
Finite automata and string matching, some on the regexp connection, okay
FA and RE, C++, many type examples
http://en.wikipedia.org/wiki/Pigeonhole_principle Wikipedia entry that goes in depth on the PHP.
The Pumping Lemma; cute poem
Wikipedia: Pumping Lemma; actual information
and decent explanation 
cs251 Handouts for weeks 5 and 6 are vaguely useful -- talks about Parsing, State Machines, NFA/ DFA. Other weeks are a bit too vague or rely too much on whatever text the prof was using. http://www.csd.uwo.ca/research/grail/links.html List of automata resources