CENG 213

Theory of Computation

Abstract automata, especially finite state machines; push-down automata; and Turing machines. Formal languages, especially context-free languages. The relationship between automata and languages. Computability and solvability.

Learning Outcomes:

  1. To be able to classify language definitions.
  2. To be able to analyze problems and provide appropriate representations for them.
  3. To be able to show abstraction ability.
  4. To be able to identify some difficult problems in computer science. 
Topics
Introduction
Sets, Relations, and Functions
Basic Proof Techniques, Closures
Languages
Deterministic and Nondeterministic Finite Automata
Regular Expressions
Context-Free Grammars
Pushdown Automata
Turing Machines
Decidability
The Chomsky Hierarchy
Computational Complexity
NP-Completeness
NP versus P