General Course Information

Topics

• Mathematical Preliminaries
• Automata
• Grammars
• Languages
• Algebra

Exercise Sheets:

Set-Theoretic & Algebraic Preliminaries

• Exercises 1: Sets, Functions, Relations (April 14, 1997)
  

Finite Automata & Regular Languages

• Exericses 2: Finite Automata & Recognizable Languages (April 21, 1997)
• Exercises 3: Incomplete & Non-Deterministic Finite Automata (May 7, 1997)
• Exercises 4: Automata & Rational Operations (May 19, 1997)

Algebra & Automata

• Exercises 5: Semigroups, Morphisms & Congruences (May 28, 1997)
• Exercises 6: Syntactic Monoids & Minimal Automata (June 4, 1997)

Languages

• Exercises 7: Grammars I (June 19, 1997)
• Exercises 8: Choose and do four problems from the 8 problems at the end of chapter four, including at least on of problems 6, 7, and 8. Number 3 is extra credit.
  (June 23, 1997)

Course Reading:

Read Chapter 5 on Pushdown Automata (which correspond to Context-Free Grammars) and Properties of Context-Free Languages
& Chapter 6 on Turing Machines (which correspond to phrase structure grammars).

It's a good idea to try some exercises as you read these chapters. Any problems from the book that you write up and turn will count as extra credit!

Topics:

• Sets, Relations, Functions, Equivalance Relations & Partition
• Finite Automata, Pumping Lemma for Regular Languages, Kleene's Theorem
• Syntactic Monoids
• Context-Free Grammars <-> Pushdown Automata
• Pumping Lemma for Context-Free Languages
• Deterministic & Non-deterministic PDAs and Turing Machines
• Turing Machines <-> Generative Grammars
• Chomsky Hierarchy & Limits of Grammars/Automata

Coming Later: Software Support for Some Techniques in this Course (and more)

• W. Thomas's AMORE (Automata, Monoids, and Regular Expressions)
• Ted Billard's Visual Computer Science
• C. Nehaniv's Semigroup Manipulation Software