Study Guide for CS 456/656 Examination April 12, 2005

Revised April 8, under construction

There will be some true/false questions.

There will be some fill-in-blanks questions.

Be able to correctly state both pumping lemmas.

Understand each of the following:

	derivation of a string
	parser
	ambiguous grammar
	grammar which respects semantics (meaning)
	Turing Machine
	NTM
	reduction
	recursively enumerable
	diagonal language
	configuration (also called instantaneous description) of a machine
	computation of a Turing Machine (sequence of configurations)

What is the Church-Turing Thesis?  Why is it important?

What is the exact definition of P?

What is the exact definition of NP?

What is the exact definition of NP-complete?

Which of the following problems (languages) are known to be NP-complete?

	a) Traveling Salesman Problem
	b) Boolean Satisfiability
	c) Binary Numerals for Prime Numbers
	d) Encodings of Turing Machines that Halt for All Inputs
	e) Satisfiable Boolean 3-CNF expressions
	f) Satisfiable Boolean 2-CNF expressions
	g) The Halting Problem

There will not be a long proof of the test.  Here is a short proof:
Prove that if a language is decidable it can be enumerated in canonical
order by some machine.  (At most half a page.)

Which of the following problems (languages) are undecidable?

	a) The Halting Problem
	b) Given two context-free grammars, do they generate the same
	language?
	c) Given one context-free grammar G and one string w, does G
	generate w?
	d) Given a loop of string, can it be untangled?
	e) Boolean Satisfiability

Some hard T/F questions.  True or False:

	The complement of a context-free language is context-free.
	The complement of a polynomial time language is polynomial time.
	The complement of an NP language is NP.
	The complement of a decibable language is decibable.
	The complement of a recursively enumerable language is recursively
	enumerable.