MACM-300 - Spring 2006 - Introduction to Formal Languages and Automata

The goal of this course is to begin to understand the foundations of computation. Various models of computation exist, all of which capture some fundamental aspect of computation. We will concentrate on three classes of models: models with finite amount of memory (finite-state automata); models with stack memory (push-down automata); and unrestricted models (Turing machines).

The notion of a formal grammar arises from the need to formalize the informal notions of grammar and language. Many formal grammars were invented: right-linear grammars, context-free grammars and unrestricted grammars. These grammars can be placed in a natural hierarchy.

Surprisingly, there is a deep connection between these grammars, the strings they generate (their language), and the models of computation introduced above. This course will also briefly cover the impact of formal language theory for many computer science applications: in compilers, natural language processing, and program verification.

More details: Course outline



Note that all homeworks are due in class on the due date.
  1. Homework #1
  2. Homework #2
  3. Homework #3
  4. Homework #4
  5. Homework #5
  6. Homework #6
  7. Homework #7
  8. Homework #8
  9. Homework #9

Important note on assignment submission and development: Do not collaborate on solving the homework. Do not discuss the solutions of the homework with others outside class. Please bring any questions you might have to class for discussion.

Textbook and References

Thanks to Tugkan Batu for his homeworks, exams and their solutions from his MACM 300 course materials. And thanks to Chung-hye Han for notes created from Sipser, and additional homework ideas. We will follow Sipser's textbook fairly closely for this course.

Syllabus and Readings

  1. Preliminaries: sets, proof methods
    • Reading: Chp 0, Sipser
    • Notes: Notes #1
  2. Finite-state automata, Regular languages
    • Reading: Chp 1, Sipser
    • Notes: Notes #2
    • Notes: Notes #3
    • Notes: Notes #4
    • Notes: Notes #5
    • Regular expressions and regular languages
    • Finite-state automata: deterministic and non-deterministic automata
    • Pumping lemma for regular languages, closure properties
    • Minimizing the size of finite-state automata
  3. Context-free grammars and context-free languages
    • Reading: Chp 2, Sipser
    • Notes: Notes #6
    • Notes: Notes #7
    • Notes: Notes #8
    • Left/right-linear context-free grammars
    • Normal forms for context-free grammars, the hardest context-free language
    • Ambiguity and parsing, deterministic context-free languages
    • Pumping lemma for context-free languages, closure properties
  4. Turing Machines, undecidable problems
    • Notes: Notes #9
    • Alternative models of computation
    • Hierarchy of languages and automata
  5. Applications (covered briefly with each topic above):
    • compilers,
    • structured databases,
    • natural language processing,
    • program verification,
    • applications of automata theory to logic

Course Expectations and Policies

anoop at