CS3350 Automata, Computability and Formal Languages

Theoretical computing models and the formal languages they characterize: Finite state machines, regular expressions, pushdown automata, context-free grammars, Turing machines and computability. Capabilities and limitations of each model, and applications including lexical analysis and parsing. Major topics include:

Regular languages, finite automata, non deterministic finite automata
Context-free languages, pushdown automata
Parsing, normal forms, ambiguity
Pumping lemmas and closure properties
Turing machines and other equivalent models
Decidable languages, non-decidable languages, recognizable languages, Chomsky hierarchy
Enumerability and countability
Introduction to complexity analysis and complexity classes

The syllabus can be found here.

Part of what should be learned in this class is to reason theoretically on programming languages and on what can be computed by a computer. We can structure our reasoning by writing things up, in the right type of mathematical language. This write-up will eventually give our own textbook to refer to. We will do the write-up collectively, using LaTeX and this git repository.

There will be 3 Homework Assignments in this class.

Homework Assignment 1 has been posted here. Boilerplate code is provided here. This assignment is due 03/01/2026 at 11:59PM MST.
Homework Assignment 2 has been posted here. This assignment is due 04/08/2026 at 11:59PM MDT.
Homework Assignment 3 has been posted here. This assignment is due 04/30/2026 at 11:59PM MDT.

There will be 3 exams in this class:

The Midterm Exam I has been organized on March 4th, 2026. The exam questions are available here.
The Midterm Exam II has been organized on April 13th, 2026. The exam questions are available here.
The Final Exam will be posted here.