CPSC 229 Fall 2007
Final Exam Information

The final exam for this course is at 1:30 PM on Wednesday, December 12. The exam will be approximately six pages long, and most people will not need the entire three-hour exam period to finish the test. The exam is cumulative. There will be some extra emphasis on material that has been covered since the third test; however, since there were only two weeks of classes after that test, you should expect more than 50% of the final exam to be on older material. You should review the information sheets for the first, second and third tests. Some of the more important material from those tests is listed below.

My office hours for the remainder of the semester are as follows:

        Tuesday, December 4:       1:30 -- 3:30
        Wednesday, December 5:    11:15 -- 1:45
        Thursday, December 6:     10:00 -- 3:00
        Friday, December 7:       11:15 -- 1:45
        Saturday, December 8:      1:00 -- 3:00

        Monday, December 10:      12:00 -- 2:30
        Tuesday, December 11:     11:00 -- 1:20  [CPSC 225 exam at 1:30]
        Wednesday, December 12:   11:00 -- 1:20  [CPSC 229 exam at 1:30]
        Thursday, December 13:    10:00 -- Noon

Here are some terms and ideas that were covered after the third test:

language generated by a grammar
production rule
non-terminal symbol
terminal symbol
start symbol
derivations and the "yields" relation ( ==> )
what it means for a string to be generated by a grammar
the language generated by a grammar
context-free grammar
Definition of a context-free grammar as G = (V,Sigma,P,S)
context-free language
finding a context-free grammar for a given language
parse trees
examples of context-free languages
every regular language is context-free
examples of languages that are not regular but are context-free
examples of non-context-free languages
the Pumping Lemma for Context-Free Languages
using the Pumping Lemma for Context-Free Languages
                                   to prove that a language is not context-free
the intersection of two context-free languages is not necessarily context-free
the context-free property of languages is preserved by union,
                                   concatenation, Kleene star, and reverse
general grammars
examples of non-context-free languages that can be generated by general grammars
finding a general grammar for a given language
proof that there are only countably many languages over a given alphabet
                                   that can be generated by grammars
Turing Machine
tape of a Turing machine
state of a Turing machine
how a Turing machine computes
how a Turing machine is used to compute a function
Turing-decidable language
Turing-acceptable language
Turing machines are equivalent in power to general grammars
Turing machines are equivalent in power to any (known) general method of computation
the Church-Turing thesis
recursive language
recursively-enumerable language
a language is recursive if and only if both it and its complement are recursively enumerable
unsolvability and the halting problem
a list of all Turing machines: T0, T1, T2, ... 
the recursively enumerable language K = { an | Tn halts when run with input an }
K is not recursive
the complement of K is a language that is not recursively enumerable
the nature of computation and computability

Some of the most important terms and ideas from the first test:

translating from logic to English and from English to logic
propositional logic; AND, OR, NOT
conditional (IMPLIES) and bi-conditional operators
truth table
converse of an implication
contrapositive of an implication
negation of  p IMPLIES q   is   p AND NOT q
laws of boolean algebra, including double negation and DeMorgan's laws
predicates predicate logic
quantifiers: FOR ALL and THERE EXISTS
negation of a quantified statement
valid arguments
proof by contradiction

Some of the most important terms and ideas from the second test:

mathematical induction and proof by induction
base case and inductive case of an induction
sets and set notation
element of a set
subset of a set
empty set
equality of sets
set operations: union, intersection, set difference, complement, cross product, power set
function from a set A to a set B
one-to-one function
onto function
bijective function, also known as one-to-one correspondence
cardinality of a set
finite sets and infinite sets
countably infinite and uncountably infinite sets
proof that the real numbers are uncountable
alphabets, symbols, strings, and languages
empty string
operations on strings: length, reverse, concatenation
operations on languages: union, intersection, concatenation, 
                                                  complement, reverse, Kleene closure

Some of the most important terms and ideas from the third test:

regular expressions
regular language
Finite-State Automaton
DFA (Deterministic Finite-State Automaton)
NFA (Non-deterministic Finite State Automaton)
transition diagram for a DFA or NFA
states in a DFA or NFA
start state
accepting state
what it means for a DFA or NFA to accept a string
definition of a DFA as a list of five things (Q, Sigma, qo, delta, F)
DFAs, NFAs, and regular expressions define exactly the same class of languages
algorithm for converting a regular expression into a DFA
algorithm for converting an NFA into a DFA
the Pumping Lemma for regular languages
using the Pumping Lemma for regular languages to prove that a given language is not regular
examples of languages that are regular and languages that are not regular

David Eck