Theory of Computing

Identifier
COMS 3310
Professor(s)
Gianfranco Ciardo

Last Updated: Spring 2025

Offered during Fall and Spring Semesters each year.

  1. Credits and contact hours: 3 credits, 4 contact hours
  2. Text book, title, author, and year: Introduction to the Theory of Computation, 3rd edition Michael Sipser
  3. Other supplemental materials: Instructor notes

Specific course information

  1. Brief description of the content of the course: Models of computation: finite state automata, pushdown automata and Turing machines. Study of grammars and their relation to automata. Limits of digital computation, unsolvability and Church-Turing thesis. Relations between classes of languages. After briefly reviewing basic background and introductory notions, the rest of the material can be divided into three main portions, each of them covered over approximately one month: regular languages, context-free languages, and Turing machines.
  2. Prerequisites or co-requisites: Minimum of C- in ComS 2280, MATH 1660, and COMS 2300 or CPRE 3100; ENGL 2500
  3. Required, elective, or selected elective? Required

Specific goals for the course

  1. Specific outcomes of instruction: By the end of the course students should have a working knowledge (ability to solve problems with rigorously justified reasoning) of the following:
  • Specifying formal languages using regular expressions, automata, or grammars. (6)
  • Manipulating language representations: e.g., building the automaton equivalent to a grammar, minimizing a deterministic finite automaton, eliminating nondeterminism in a Turing machine). (1)
  • Recognizing the power and limitations of regular, context-free, recursive, and recursively-enumerable languages.
  • Understanding the halting problem and its implications to computer science.
  • Understanding the power of nondeterminism.
  • Using the pumping lemma to prove that a language is not regular/context-free.
  • Using reduction to prove that a language is not recursive/recursively-enumerable.

Brief list of topics to be covered

  • The concepts of formal languages as sets of strings over an alphabet, of grammar as language generators, and of automata as language acceptors.
  • Finite automata, and their relation to regular expressions and regular grammars.
  • Eliminating nondeterminism in finite automata, minimizing deterministic finite automata.
  • The pumping lemma for regular languages.
  • Closure properties for regular languages.
  • Context-free grammars, and their relation to pushdown automata.
  • Derivations, parse trees, and ambiguity for context-free languages.
  • The pumping lemma for context-free languages.
  • The importance on nondeterminism in pushdown automata.
  • Closure properties for context-free languages.
  • Turing machines and computational universality.
  • The Church-Turing thesis.
  • Decidable vs. semi-decidable languages, solvable vs. semi-solvable problems.
  • Using reduction to prove that a language is not decidable.