CptS 317: Automata and Formal Languages
Course Information
Credit Hours: 3
Semester Taught: Fall/Spring
Textbook: Introduction to the Theory of Computation, Third Edition, Michael Sipser. 2013
Course Objectives
- Introduce concepts in automata theory and theory of computation
- Identify different formal language classes and their relationships
- Design grammars and recognizers for different formal languages
- Prove theorems in automata theory and language properties
- Determine the decidability and intractability of computational problems
Prerequisites
- CptS 122/132 – Data Structures
- Math 216 – Discrete Structures
Learning Outcomes
At the conclusion of this course students will:
- Have acquired a fundamental understanding of the core concepts in automata theory and
formal languages - Be able to design grammars and automata (recognizers) for different language classes
- Be able to identify formal language classes and prove language membership properties
- Be able to prove theorems establishing key properties of formal languages and automata
- Have acquired a fundamental understanding of core concepts relating to the theory of computation and computational models including decidability and intractability
Topics
- Introduction to automata theory
- Finite Automata (DFA and NFA)
- Regular expressions and languagues
- Properties of regular languages: pumping lemma, closure properties, decision properties, equivalence and minimization of automata
- Context-free grammars and languages
- Pushdown Automata
- Properties of context-free languages
- Turing machines and extensions
- Undecidability, diagonalization, problem reduction
- Intractable problems: P and NP, NP-completeness
Weekly Schedule
This is an example of what the week-by-week schedule of topics and assignments would look like.
| WEEKS | TOPICS | ASSIGNMENTS |
|---|---|---|
| 01 | Intro to course, intro to computation theory | HW0 (survey) out |
| 02 | Review of math concepts, proof techniques, finite automata | HW0 in; HW1 out |
| 03 | Finite Automata | No class 9/2; HW1 in, HW2 out |
| 04 | Regular Expressions | HW2 in, HW3 out |
| 05 | Nonreguar Languages | HW3 in |
| 06 | Context-free Languages | Mid-term 1 on 9/25 |
| 07 | Context-free Grammars | HW4 out |
| 08 | Pushdown Automata | HW4 in, HW5 out |
| 09 | CFG and PDA equivalence | HW5 in |
| 10 | Minimization of Automata; Deterministic CFL | Review for Mid-term 2 |
| 11 | Turing Machines I | Mid-term 2 (10/28); HW 6 Out |
| 12 | Turing Machines II | HW6 in |
| 13 | Decidability | No class 11/11; HW 7 out |
| 14 | Reducibility | HW 7 in |
| 15 | Thanksgiving break | |
| 16 | Time Complexity, Review | Practice |
| 17 | Finals Week | Final Exam on Dec 9 |