Prerequisite Topics

• Trees, algorithms and recursion
• Functional programming
• Basic concepts of set theory
• Reading and writing formal mathematical proofs (of the sort studied in a course on formal logic)
• Reading and writing informal mathematical proofs (as found in typical mathematics books)
• Mathematical induction

High-level Goals

• To teach students the basic concepts and techniques of formal language theory
• To further develop students' competence at reading and writing mathematical proofs

Knowledge and Skills Acquired: Mastery

• Basic set theory
• Induction principles for the natural numbers
• Trees and inductive definitions
• Symbols, strings, alphabets and (formal) languages
• String induction principles
• Regular expressions and languages
• Simplification of regular expressions
• Finite automata and labeled paths
• Isomorphism of finite automata
• Algorithms for checking acceptance of strings by finite automata, and for finding accepting paths for strings in finite automata
• Simplification of finite automata
• Proving the correctness of finite automata
• Empty-string, nondeterministic and deterministic finite automata
• Closure properties of regular languages
• Equivalence-testing and minimization of deterministic finite automata
• The pumping lemma for regular languages
• (Context-free) Grammars, parse trees and context-free languages
• Proving the correctness of grammars
• Simplification of grammars
• Experimenting with regular expressions, finite automata and grammars using the Forlan toolset

Knowledge and Skills Acquired: Familiarity

• Applications of finite automata and regular expressions
• Isomorphism of grammars
• A parsing algorithm
• Ambiguity of grammars
• Closure properties of context-free languages
• Converting regular expressions and finite automata to grammars
• Chomsky Normal Form of grammars
• The pumping lemma for context-free languages
• Basic results on recursive and recursively enumerable languages and the undecidability of the halting problem