Current Catalog Description

Formal study of theoretical computational models: finite automata, pushdown automata, and Turing machines. Study of formal languages: regular, context-free, and decidable languages. Prerequisite: CSE 140.

Instructor: Arielle Carr (Spring 2021)


Micheal Sipser, "Introduction to the Theory of Computation", 3rd Edition, ISBN 978-1133187790



CSE 318 substantially supports the following student enabled characteristics

A. An ability to apply knowledge of computing and mathematics appropriate to the discipline


Students will:

  1. Understanding theoretical capabilities and limitations of algorithms as a function of the problems they can/cannot solve
  2.  Formal understanding of the notion of nondeterministic computation
  3.  Understanding the classes of machines, as per the Chomsky hierarchy, their capabilities and limitations
  4.  Understanding the principles of formal languages


Major Topics Covered in the Course

  1.  Regular Languages
    • Regular expressions
    • Finite automata
    • Non regular expressions
  2. Context-free languages
    • Context-free grammars
    • Pushdown automata
    • Non context-free languages
  3.  Computational Theory
    • Turing machines
    • Decidable languages
    • Turing-recognizable languages
    • Turing-enumerability
    • Definition of algorithm
  4.  Non-decidable languages
    • Halting problem
    • Diagonalization methods

Assessment Plan for the Course


The students are giving weekly homework assignments on each of the topics covered in the course. There are two exams and a final exam.

How Data in the Course are Used to Assess Program Outcomes: (unless adequately covered already in the assessment discussion under Criterion 4

Each semester I include the above data from the assessment plan for the course in my self-assessment of the course. This report is reviewed, in turn, by the Curriculum Committee.