About

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.

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

Instructor(s)

Assistant Professor

Assistant(s)

Other Second Year Courses