Correspondence of lectures and chapters of our textbook
                                  or
                          Suggested Reading


(As the chapters in the book are called lectures, in what follows
 Fö stands for a lecture, Ch for a chapter.)


Fö 1  -  Ch 2, except for "Operations on Sets".
Fö 2  -  Ch 3,4, except for "Some Closure Properties...", part of Ch 5.
         (See the comment related to p.25 in our errata for the books.)
Fö 3  -  Ch 5,6, slides on NFA's with epsilon transitions.
         (The slides available from
         http://www-und.ida.liu.se/~TDDA89/Notes/minor.slides.html).

Fö 4  -  Slides on NFA's with epsilon transitions.
      -  Operations on sets from Ch 2,
         slides on regular expressions,
         Ch 7, Ch 8 - but restricted to regular expressions.
         (also "More Closure Properties" from Ch 6).
      -  Slides "From finite automata to regular expressions" 

Fö 5  -  Slides "From finite automata to regular expressions" 
         Ch 13 (DFA State Minimization).

Fö 6  -  Repeat what you know about equivalence relations and
         equivalence classes.
         Ch 13 (DFA State Minimization), Ch 14 (A Minimization Algorithm)
         Ch 15,16 (Myhill-Nerode ...)
         Closure properties of regular languages.  The book discusses
         them a bit differently and this is spread in various places.
         Ch 11, 12 (Limitations of Finite Automata, Pumping Lemma)

  [Easter break]

Fö 7  -  Ch 10 (Homomorphisms).
         Ch 19 (Context-Free Grammars, but without pushdown automata),
         see also our errata: 

              p. 131, l. 6..8
                It is incorrectly stated that a grammar is ambiguous if
              there exist different derivations of the same string.
              "Derivations" should be replaced by "leftmost derivations".
              (Equivalently, by "rightmost derivations" or "parse trees").

Fö 8     Slides on parse trees and ambiguity.
         Ch 21 (normal forms),
             (we skip most of the sub-chapter on Greibach Normal form).
         Removing useless symbols - only outlined in the compendium
            (in the solution suggestions), explained in the Hopcroft &
            Ullman book, the beginning of Chapter 35 explains half of
            the solution.

[updated on 2007-04-19]

Fö 9     Ch 21
         (Removing left recursion - moved to the lecture on LL parsing)
         Ch 23 (pushdown automata) and the relevant part of Ch 19.
         
Fö 10    Ch 23
         Ch E  (Final State versus Empty Stack)
         Slides "PDA for a given CFG" 
         Ch 25 (from PDA's to CFG's) is relevant, but we just mention
         its main result.
         Brief discussion of deterministic context-free languages,
         done differently from Ch F.
         The pumping lemma for CFL, Ch 22

Fö 11 
         Closure properties of CFL's from Ch 27
         Slides on LL parsing
         A (simple) generalization of CFG's - right hand side of a
         production is a regular expression.

Fö 12 
         The chapter on LR(0) parsing, to be found in the compendium.
         Slides on LR(0) parsing.
         Additional reading: Ch 26 "Parsing" provides another view on
         shift-reduce parsing.

Fö 13  
         The chapters on LR(0) and LR(1) parsing from the compendium.
         The slides on LR(0) and LR(1) grammars.

Fö 14  
         Ch 28,29 on Turing Machines.

Fö 15,16  
         Ch 28,29,30,31 on Turing Machines.
         Slides:  an example Turing Machine,
                  (un)decidable problems.