CIS 570: Introduction to Formal Language Theory

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