Theory of Computing

Course
Course Catalog URL: 
http://catalog.iastate.edu/azcourses/com_s/
Identifier: 
COM S 3310
Professor(s): 
Jack Lutz

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: Jack Lutz
  3. Text book, title, author, and year: Introduction to the Theory of Computation, Michael Sipser.
  4. Other supplemental materials: Notes 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.