Skip to main content
CPE
410
Theory of Computation
To introduce the student of computer science to, and to provide some depth in theoretical models for computation. This course provides unified coverage of the hierarchies of formal languages and non-deterministic automata, emphasizing the correspondence between them. The theory of computability and decidability is introduced. Topics covered include: Role of formal languages and automata in the study of computability and complexity. Finite state automata and regular expressions. Pushdown automata and context-free grammars. Turing machines and computable functions.
Prerequisites:
0612300
0612410
(3-0-3)

Credits and Contact Hours

3 credits, 43 hours

Course Instructor Name

Prof. Tassos Dimitriou

Textbook

Introduction to the Theory of Computation, Michael Sipser, 3rd Edition

Catalog Description

The goal of the course is to introduce the student in the theoretical models for computation. This course provides coverage of the hierarchies of formal languages and non-deterministic automata, emphasizing on the correspondence between them. The theory of computability and decidability is introduced. Other topics include: Role of formal languages and automata in the study of computability and complexity. Finite state automata and regular expressions. Pushdown automata and context-free grammars. Turing machines and computable functions. Overview of algorithms.

Prerequisite

CpE-300

Specific Goals for the Course

Upon successful completion of this course, students will be able to:

  • Develop understanding of finite state systems, their specifications and properties and ability to build them to meet a task and convert between different types of finite state systems (Student outcomes: 1, 2).
  • Demonstrate understanding of regular expressions and their connection to finite state machines and ability to build machines to recognize regular expression patterns and vice versa (Student outcomes: 1, 2).
  • Demonstrate understanding of context-free grammars, languages, derivations and parse trees and ability to construct grammars for specific tasks (Student outcomes: 1, 2).
  • Demonstrate understanding of pushdown store automata and the associated LIFO data structure and the connection with context-free grammars and ability to construct such machines for specific tasks and convert between such machines and context-free grammars (Student outcomes: 1, 2).
  • Learn machines and languages of the Chomsky Hierarchy (Student outcomes: 1).
  • Develop understanding of Turing machines and recursive and recursively enumerable languages and phrase structure grammars (Student outcomes: 1).
  • Develop understanding of the principles of computability and complexity including decision problems, halting problems and basic complexity classes such as P and NP (Student outcomes: 1).
  • Recognize of the need for and practice in formal specification (Student outcomes: 1, 7).
  • Learn the concept of and practice with programming with limited resources or on restricted systems (Student outcomes: 1, 2).
  • Understand the limits of computation (Student outcomes: 1)

Topics to Be Covered

  • Mathematical notions and terminology, theorems, proofs, and proof types
  • Grammars, automata, computability, complexity and languages
  • Finite-state languages and finite-state automata
  • Context-free languages, pushdown automata, non-context-free languages
  • Recursively enumerable and recursive languages, and Turing machines
  • Closure properties, pumping lemmas, and decidability, the halting problem
  • Reducibility, undecidability, undecidable problems, mapping reducibility
  • Introduction to computability, the recurrence theorem, Turing decidability.