CS-352 — Theory of Automata and Formal Languages

Course Description

This course introduces the formal models used to describe computation and language: finite automata and regular languages, regular expressions, context-free grammars and pushdown automata, and Turing machines as a model of general computation. Students learn to construct and minimize automata, prove properties of languages using tools such as the pumping lemma, and understand the boundary between decidable and undecidable problems.

These foundations underpin much of computer science — compiler design, formal verification, parsing, and complexity theory all build directly on the models introduced in this course.

Course Outcomes / Objectives

Construct deterministic and non-deterministic finite automata for a given regular language.
Convert between regular expressions, finite automata, and regular grammars.
Prove that a language is not regular using the pumping lemma.
Design context-free grammars and pushdown automata for context-free languages.
Explain the Turing machine model of computation and the notion of decidability.

Text Books

Introduction to the Theory of Computation (3rd ed.) — Michael Sipser — primary textbook
Introduction to Automata Theory, Languages, and Computation (3rd ed.) — Hopcroft, Motwani & Ullman — supplementary reference