CS 659: Introduction to the Theory of Computation
(Coordinator: Mark Bochert)
Catalog description
Review of sets, relations, and languages. Induction and diagonalization. Finite automata, context-free languages, pushdown automata. Basic complexity theory.
Course Topics and Student Outcomes
Models & Abstractions (1)
- Formally define and reason about discrete mathematical structures and concepts (sets, relations, functions, cardinalities, counting.)
- Synthesize and evaluate elementary mathematical arguments as they apply to formal models of computation
- Determine a language's location in the Chomsky hierarchy (regular languages and context-free languages)
- Prove that a language is in a specified class and that it is not in the next higher class
- Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs
Evaluation
- Weekly homework assignments (20%)
- Weekly quizzes (40%)
- Two exams (40%)
Topics
-
Review of basic discrete mathematics including:
- Logic, sets, relations, functions, induction and counting
-
Limitations of computation:
- Diagonalization method, cardinality, halting problem
-
Models of computation:
- Alphabets and languages
- Regular languages and regular expressions
- Deterministic and nondeterministic finite automata
- Context-free languages and pushdown automata
Textbooks
- James L. Hein, Discrete Structures, Logic, and Computability, 3rd Ed.