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:
grammars
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
parsing
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 tautology 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 counterexample 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