CS 420 Theory of Computing

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