Revised Nov 1, 2016

CS 462: Formal Languages and Parsing

Watch a video introduction to this course on YouTube.

General description

Building on CS 360, this course discusses more advanced topics in formal languages and automata theory, including applications, compiler writing, and parsing methods.

Logistics

Audience

• CS major students. Usually taken in fourth year.

Normally available

• Winter Term

Related courses

• Pre-requisites: CS 360 or 365 or equivalent course
• Successors: Graduate courses in compiler writing or formal languages

For official details, see the UW calendar.

Software/hardware used

• --

Typical reference(s)

• J. Shallit, A Second Course in Formal Languages & Automata Theory, Cambridge University Press

Required preparation

At the start of the course, students should be able to

• Prove statements by induction
• Explain basic computing models, such as finite automata, pushdown automata, and Turing machines
• Describe grammars and machine models

Learning objectives

At the end of the course, students should be able to

• Explain more about basic computer models
• Describe the theory behind modern parsing methods
• Solve problems in the theory of combinatorics on words

Typical syllabus

Properties of strings (3 hours)

• Outline of formal language theory
• Strings, machines, proofs by induction
• Combinatorics on words
• Thue's problem

Regular sets (10 hours)

• Closure of regular sets under quotient, substitution, and inverse homomorphism
• Decision algorithms for regular sets
• Myhill-Nerode theorem
• Minimization of finite automata
• Finite-state transducers

Context-free languages (6 hours)

• Coping with ambiguity
• Inherently ambiguous CFL's
• Closure of context-free languages under substitution, inverse homomorphism, and intersection with regular sets
• Decision algorithms for context-free languages
• Parsing arbitrary context-free grammars
• Decidability results for CFG's

Parsing (6 hours)

• Phases of compilation
• Top-down parsing
• LL(1) grammars
• Bottom-up parsing
• LR(0) grammars and LR(k) grammars

Chomsky hierarchy (3 hours)

• Left- and right-regular grammars
• Unrestricted (Type 0) grammars
• Equivalence of Type 0 grammars and Turing machines
• Context-sensitive languages
• Linear bounded automata

Deterministic context-free languages (3 hours)

• Normal forms
• Closure under complementation
• Relationship to LR(0) grammars

Other language classes (5 hours)

• L-systems
• Applications to computer graphics
• Rational series