CPSC 229, Fall 2000                        Information for the final exam
-------------------------------------------------------------------------

The final exam for CPSC 229 is scheduled for 1:30 to 4:30 on Thursday,
December 14.  The exam will be five or six pages long -- that is, about
twice as long as one of our in-class tests.  The exam counts for 25% of
the total grade for the course.  About 50% of the test will be on old
material from the three in-class tests and the other 50% will be on 
stuff that we've covered since the third test.  This includes Chapters
5 and 6 from the textbook.  Here is a list of some of the terms and ideas
from Chapters 5 and 6 that you should know:

   Grammars
   Context-free grammars
   General grammars
   Start symbol
   Production rule
   Non-terminal symbols and terminal symbols
   Derivation of a string, according to a grammar,
   Language generated by a grammar
   Context-free language
   Every regular language is context-free
   Examples of context-free grammars
   Examples of languages that are context-free but not regular
   The union or concatenation of two context-free languages is context-free
   The Kleene-star of a context-free language is context-free
   BNF (Backus-Naur Form)
   BNF production rules and BNF grammars
   Equivalence of BNF and context-free grammars
   Parsing
   Parse trees
   Ambiguous grammars
   Examples of languages that are not context-free
   Examples of general grammars
   Examples of non-context-free languages that are generated by grammars
   Turing machines
   Rules for a Turing machine
   Tape of a Turing machine
   Start state and halt state
   Transition diagram for a Turing machine
   How a Turing machine computes
   Running a Turing machine with input w
   Turing-acceptable language
   Turing-decidable language
   Equivalence of various forms of computation
   Two-tape Turing machines
   Recursively enumerable (r.e.) language (synonym for Turing-acceptable)
   Recursive language (synonym for Turing-decidable)
   A language is recursive iff both it and its complement are r.e.
   Recursive and recursively enumerable sets of natural numbers
   String representation of a Turing machine
   The "standard" Turing machines T1, T2, T3, ...
   A language that is recursively enumerable but not recursive
   A language that is not recursively enumerable
   The Halting problem
   Recursive unsolvability of the Halting problem
   The nature of computation
   
I suggest that you review old tests, homework, and homework solutions.
Here are a few topics that will NOT be on the final exam:

   Proof by induction.
   Recursion in programming (Section 3.4).
   Anything about Java/C++ programming (such as Sections 2.3 and 2.5).
   Deduction and formal proofs (Section 1.5).
   Russell's paradox and Goedel's theorem.