CS 462 | SCS

Building on CS 360, this course discusses more advanced topics in formal languages and automata theory, with applications to compiler writing. In particular, several practical parsing methods are discussed.

Intended Audience

CS 462 is normally taken in a student's fourth year. This course should be of interest to students planning further studies in computer science.

Related Courses

References

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

Schedule

Outline

Properties of Strings (3 hours)

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

Regular Sets (9 hours)

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

Context-free Languages (6 hours)

Review. 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 (9 hours)

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

The 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)

Other Language Classes (3 hours)