Course Syllabus

Course Description

This course introduces the theory of computation through a set of abstract machines that serve as models for computation - finite automata, pushdown automata, and Turing machines - and examines the relationship between these automata and formal languages. Additional topics beyond the automata classes themselves include deterministic and non-deterministic machines, regular expressions, context free grammars, undecidability, and the P = NP question.

Course Objectives

This course introduces the mathematical foundations of computation. By the end of this course, students will be able to: 1. Develop a Formal Understanding of Computation 2. Analyze and Design Finite-State Computational Models 3. Model Hierarchical and Recursive Structures 4. Understand the Limits of Algorithmic Computation 5. Classify Problems by Computational Complexity 6. Strengthen Formal Reasoning and Proof Skills Beyond theory, the course emphasizes how these abstract models power real systems including: * Search engines and pattern matching * Compilers and programming languages * Network protocol verification * Input validation and cybersecurity * Artificial intelligence parsing systems The goal is not memorization of definitions, but understanding how different computational models capture different levels of machine capability.

Key Concepts

1. Finite Automaton (FA)
2. Deterministic Finite Automaton (DFA)
3. Nondeterministic Finite Automaton (NFA)
4. Regular Language
5. Regular Expression (RE)
6. Context-Free Grammar (CFG)
7. Pushdown Automaton (PDA)
8. Turing Machine (TM)
9. P vs NP Complexity
10. Decidable Language

Learning Outcomes

1. Define and apply the fundamental concepts of formal languages, including alphabets, strings, language operations, and mathematical notation used in automata theory.
2. Design, analyze, and prove properties of deterministic and nondeterministic finite automata, and demonstrate equivalence between automata and regular expressions.
3. Construct and analyze context-free grammars and pushdown automata, including transformations and applications of the pumping lemma for context-free languages.
4. Model computation using Turing machines, distinguish between decidable and recognizable languages, and apply reduction techniques to prove undecidability results.
5. Classify problems into complexity classes (P, NP, NP-complete), apply polynomial-time reductions, and explain the theoretical and practical implications of the P vs NP question.

Recommended Textbooks

An introduction to formal languages and automata; Peter Linz, Susan H. Rodger; (7th Edition), Jones & Bartlett Learning, [2023]; ISBN 9781284231601 Introduction to Theory of Computation, Anil Maheshwari, Michiel Smid, 2024