Michigan State University
CPS 360 - Final Examination Review

Instructor: Travis Doom

Summer Semester, 1998

This document contains a list of topics and questions that could appear on the final examination in CPS 360. The majority of the test material will cover the topics listed below, but any material appearing in the textbook (Ch. 1 - 11) or discussed in class may appear on the exam. The material since the midterm (Ch 9 - 11) may be covered more throughly than earlier material. The management reserves the right to include questions not explicitly included in this list.

1.
Any of the topic/questions from the Midterm Review Sheet may appear on the final exam.
2.
Given a Turing Machine (TM) M and possibly an input x:
(a)
formally and explicitly list the components of the formal definition of the abstract machine
(b)
describe the language accepted by M
(c)
does M accept or recognize/decide L(M)?
(d)
determine the initial configuration of M(x)
(e)
show the computation M(x). Does M(x) halt/crash/loop? Is x accepted by M(x)?

3.
Given a language L or a function F:
(a)
construct a TM that computes $\mathcal{X}_L$(the characteristic function of L)
(b)
construct a TM that computes the total or partial function F for some data representation (unary, binary, etc.)

4.
Be able to construct, perform computations on, and discuss the advantages/disadvantages of variations on Turing Machines, including:
(a)
multi-tape Turing Machines
(b)
nondeterministic Turing Machines (NTMs)
(c)
the Universal TM Tu

5.
Given two TMs M1 and M2 be able to construct a TM which accepts: L(M1) $\union$ L(M1), L(M1) $\intersection$ L(M2), L(M1) - L(M2), etc.

6.
Understand the classes of recursive and recursively enumerable languages:
(a)
given a language L or a TM M with L(M) = L, is L a recursively enumerable (RE) language?
(b)
given a language L or a TM M with L(M) = L, is L a recursive language?
(c)
why is a language that is enumerable recursively enumerable?
(d)
why is a language that is enumerable in canonical order recursive?

7.
Understand the significance of undecidable problems:
(a)
define the halting problem and describe why the fact that it is unsolvable is important
(b)
give an example of a language which is recursively enumerable, but not recursive
(c)
give an example of a language which is not recursively enumerable
(d)
discuss the cardinality of the various classes of languages and the implications of these facts
(e)
understand the relationship between decision problems and language recognition

8.
Understand context-sensitive grammars (CSGs):
(a)
given a CSG, what is the language it describes
(b)
given a language, construct a CSG that generates it
(c)
what is the primary difference between CSG and unrestricted grammars?

9.
Understand unrestricted/phase-structure grammars:
(a)
given an unrestricted, what is the language it describes
(b)
given a language, construct an unrestricted that generates it

10.
Be familiar with the classes of languages and their closure properties
(a)
understand the Chomsky hierarchy
(b)
be able to list the classes of languages, their corresponding grammars, and the abstract machines that accept them
(c)
what does the statement ``The set of recursively enumerable languages is not closed under complement'' mean?

11.
Given a list of statements about the properties of a language or TM or just about anything else, such as relations and functions, determine whether each is correct or not (True/False questions).

12.
Be able to present the ``high-level'' concepts discussed in class, such as:
(a)
what is it about a language that makes it recursively enumerable?
(b)
why isn't their a pumping lemma for recursive languages?
(c)
what is the significance of the Church-Turing Thesis?
(d)
what is non-determinism?

13.
One or more problems on the final may be problems taken directly from the assigned homework

14.
If an extra credit problem appears on the exam, it may concern time and space complexity, P and NP, complete problems, reduction, or similar ``advanced'' concepts

Travis Doom, travis.doom@wright.edu.

Last modified: 06/29/98