CSE322: Introduction to Formal Models in Computer Science

Catalog Description: Finite automata and regular expressions; context-free grammars and pushdown automata; nondeterminism; Turing machines and the halting problem. Emphasis on understanding models and their applications and on rigorous use of basic techniques of analysis. Induction proofs, simulation, diagonalization, and reduction arguments.

Prerequisites: CSE 321.

Portions of the CSE322 web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly creditied. The CSE322 Web: © 1993-2019, Department of Computer Science and Engineering, Univerity of Washington. Administrative information on CSE322 (authentication required).