Forlan Textbook and Lecture Slides

Fall 2008

Note: I'll be revising the book and slides, on a section-by-section basis, as the fall progresses. Last fall's draft is still available.

• Textbook
• Lecture Slides
  • GNU Free Documentation License
  • Preface (view/print)
  • Chapter 1: Mathematical Background
    • (1.1) Basic Set Theory (view/print)
    • (1.2) Induction (view/print)
    • (1.3) Inductive Definitions and Recursion (view/print)
  • Chapter 2: Formal Languages
    • (2.1) Symbols, Strings, Alphabets and (Formal) Languages (view/print)
    • (2.2) Using Induction to Prove Language Equalities (view/print)
    • (2.3) Introduction to Forlan (view/print)
  • Chapter 3: Regular Languages
    • (3.1) Regular Expressions and Languages (view/print)
    • (3.2) Equivalence and Simplification of Regular Expressions (view/print)
    • (3.3) Finite automata and Labeled Paths (view/print)
    • (3.4) Isomorphism of Finite Automata (view/print)
    • (3.5) Checking Acceptance and Finding Accepting Paths (view/print)
    • (3.6) Simplification of Finite Automata (view/print)
    • (3.7) Proving the Correctness of Finite Automata (view/print)
    • (3.8) Empty-string Finite Automata (view/print)
    • (3.9) Nondeterministic Finite Automata (view/print)
    • (3.10) Deterministic Finite Automata (view/print)
    • (3.11) Closure Properties of Regular Languages (view/print)
    • (3.12) Equivalence-testing and Minimization of Deterministic Finite Automata (view/print)
    • (3.13) The Pumping Lemma for Regular Languages (view/print)
    • (3.14) Applications of Finite Automata and Regular Expressions (view/print)
  • Chapter 4: Context-free Languages
    • (4.1) Grammars, Parse Trees and Context-free Languages (view/print)
    • (4.2) Isomorphism of Grammars (view/print)
    • (4.3) A Parsing Algorithm (view/print)
    • (4.4) Simplification of Grammars (view/print)
    • (4.5) Proving the Correctness of Grammars (view/print)
    • (4.6) Ambiguity of Grammars (view/print)
    • (4.7) Closure Properties of Context-free Languages (view/print)
    • (4.8) Converting Regular Expressions and Finite Automata to Grammars (view/print)
    • (4.9) Chomsky Normal Form (view/print)
    • (4.10) The Pumping Lemma for Context-free Languages (view/print)
  • Chapter 5: Recursive and Recursively Enumerable Languages
    • (5.1) Programs and Recursive and Recursively Enumerable Languages (view/print)
    • (5.2) Closure Properties of Recursive and Recursively Enumerable Languages (view/print)
    • (5.3) Diagonalization and Undecidable Problems (view/print)