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:**

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: T_{0}, T_{1}, T_{2}, ... the recursively enumerable language K = { a^{n}| T_{n}halts when run with input a^{n}} 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, q_{o}, 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