Forlan Textbook and Lecture Slides

Fall 2007

• Textbook
• Lecture Slides
  • GNU Free Documentation License
  • Preface (view/print)
  • Chapter 1: Mathematical Background
    • (1.1) Basic set theory (view/print)
    • (1.2) Induction principles for the natural numbers (view/print)
    • (1.3) Trees and inductive definitions (view/print)
  • Chapter 2: Formal Languages
    • (2.1) Symbols, strings, alphabets and (formal) languages (view/print)
    • (2.2) String induction principles (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)