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.