CS 420 Theory of Computing

From Computer Science
Jump to: navigation, search

Catalog Description

A sampling of the different areas of theoretical computer science: finite state concepts, formal grammars and automata, computability, Turing machines, and program verification. Prerequisite - C or better in CS 202 and CS 303.

Prerequisites

Willingness to work hard. Knowing how to write a formal mathematical proof.

Standard Content

Course Outline

  • closely follows the first 5 Chapters of the course textbook (see below), except that some topics are not covered in class
  • Regular languages:
  • Finite automata (DFA):
  • Formal definition of finite automata, examples
  • Formal definition of computation, designing finite automata
  • Regular operators
  • Nondeterminism:
  • Formal definition of a nondeterministic finite automaton (NFA)
  • Equivalence of NFAs and DFAs (with proofs)
  • Closure under regular operations (with proofs)
  • Regular expressions:
  • Formal definition of a regular expression
  • Equivalence with finite automata (with proofs)
  • Nonregular languages
  • The pumping lemma for regular languages (with proofs, students are expected to master how to use this lemma that certain languages are nonregular)
  • Context-free languages:
  • Context-free grammars (CFG)
  • Formal definition of CFGs, examples of CFGs
  • Chomsky normal form
  • Pushdown automata (PDA)
  • Formal definition of PDA, examples
  • Equivalence of PDAs with CFGs, proof not covered in class
  • Non-context-free languages:
  • Pumping lemma for CFGs (students are expected to master how to use this lemma that certain languages are not context-free)
  • Church-Turing thesis:
  • Turing machines: formal definition, examples
  • Variants of Turing machines, nondeterministic Turing machines, enumerators
  • Definition of an algorithm
  • Decidable languages:
  • Decidable languages concerning regular languages, context-free languages
  • Undecidability:
  • Diagonalization method, examples of undecidable and Turing-unrecognizable languages
  • Reducibility:
  • Some undecidable problems, reduction via computation histories
  • Computable function, mapping reducibility

Learning Outcomes

  • Basic understanding of fundamental computational models such as DFAs, NFAs, Turing machines, etc. and their properties.


Important Assignments and/or Exam Questions

  • Give a formal definition of a finite automaton.
  • Let Bn = {ak | k is a multiple of n}. Show that for each n ≥ 1, the language Bn is regular.
  • Use the pumping lemma to show that the language {0n1n0n1n} is not context free.
  • Let Σ = {1,2,3,4} and C = {w ∈ Σ* | in w, the number of 1s equals the number of 2s and the number of 3s equals the number of 4s}. Show that C is not context-free.
  • Define the following terms: (a) Turing-recognizable language, (b) co-Turing-recognizable language, (c) decidable language, (d) enumerator, (e) linear bounded automaton.
  • What does it mean that language A is mapping reducible to language B?
  • Let Q = {<M1,M2> | M1 and M2 are TMs and L(M1) = L(M2)}. Give a proof that Q is undecidable. You are allowed to use results from class.

Standard resources

  • Introduction to the Theory of Computation, 3rd Edition, by Michael Sipser. ISBN 978-1133187790