Theory of Computing

COM S 331

Offered during Fall and Spring Semesters each year.

  1. Credits and contact hours: 3 credits, 4 contact hours
  2. Instructor’s or course coordinator’s name: Gianfranco Ciardo
  3. Text book, title, author, and yearIntroduction to the Theory of Computation, Michael Sipser.
  4. Other supplemental materialsNotes for ComS 331 Theory of Computing (instructor notes, 76 pages)

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.
  2. Prerequisites or co-requisites: Minimum of C- in Com S 228, MATH 166, and in COM S 230 or CPR E 310; ENGL 250
  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.