EDIT: Oops...I thought she was asking for a list of ALL topics that would be on the final. :/ Eh, I'll leave it in case it helps.

What to study for the final:

Covering Chs 1-5, Generally. Not covering Pumping lemmas (either of them), PDAs (push down automata), Chompsky normal form, ambiguity, Post correspondance problem (5.2) or LBA (can't remember what that stands for. But if you come across anything like LBA you can probably ignore it.)

Ch 1: Regular languages

Know the set of languages accepted by DFAs and NFAs. Know their formal definitions (5-tuples) and definitions of their computations. The languages they accept. Given a description of a machine, construct a DFA or NFA, and vise verse. Know the equivalence between DFAs and NFAs and be able to build one from the other, (NFA -> DFA, use subset construction).
 
Know the formal defn. of regular expressions (Regexs). Know how to convert them into NFAs (using machine construction) and how to convert DFAs into Regexs (by state elimination.) Reason about the languages that REs describe (whatever that means.) Know the closure properties (REs closed under Union, concatenation, star, intersection, set difference, complement, etc. These operations yield regular languages when you use regular languages, but don't go the other way. If you get a regular language RE, you can't conclude that any languages you created it with are regular.
Some non-regular languages to remember (in case you need them): (0^n)(1^n) or the set of Palindromes.

Ch. 2. Context Free Languages

Know the formal definition. Given a desc. be able to write a Context Free Grammar for it. Know that CFGs are equivalent with Push down automata even though we don't need to know PDA topics. Know that CFLs are closed under union, star and concatenation but not intersection, set difference or compliment.

--- MOST EMPHASIS IS ON THE TOPICS BELOW. ---

Ch 3. Turing Machines

Know the formal defintion, and the two ways for a TM to reject a string (moving into a reject state or entering into an infinite loop). You will not need to draw out any TMs on the exam (they'd be too big). Know that TMs are equivalent to algorithms, and that they are models for actual programs and computers like the one you're on right now. Hint: If you need to design a TM, think of how you'd write a program to do it). Know robustness: how to show a modified TM isn't more powerful than a regular TM. Example: 2+ tapes is just as good as one tape, because you can just splice them together and put dots over the symbols where the other machine's heads should be, and move the dots. Nondeterministic TMs and tapes extending infinitely in either direction are not more powerful - it would probably be wise to think about how to change a modified TM into a regular TM, for example by splicing the tapes).

Ch. 4 - Decidability

A language L is decidable if some TM decides it, meaning it halts on it in an accept or reject state, and thereby accepts and rejects all input. The other alternative is that the machine doesn't halt (goes into an infinite loop).

Regular langs are contained within CFLs are contained within Decidable langs are contained within Turing-regognizable langs (langs which have a TM that recognizes them, meaning it will accept strings in the language, but may go into an infinite loop for strings which are not in the language and not just reject them. Remember decidable languages halt on (accept or reject) ALL input.)

Decidable languages are closed under compliment - you just switch the accept and reject states.

Know some languages that are decidable, in case you need them: Acceptance(for DFAs), Empty (for DFAs) and Equality (for DFA) problems (which are languages).

Know that there are even some languages that are not Turing Recognizable, like the DIAG language we covered in class.

Ch 5. Reductions.

Given two languages A and B, there are 4 ways to understand A < B (< should actually be the greater than or equal to symbol):
1) A is reducible to B.
2) You can solve A by using the solution to B.
3) If you can solve B, you can solve A.
4) B is at least as hard as A.
But Not the other way around!

Implications of A < B:
1) If A is undecidable, B is undecidable.
2) If B is decidable, A is decidable.
Don't go the other way around! These two things are the only implications you can make.

Use reduction to show L is undecidable in the following way:

1) Select a known undecidable problem/language, such as A_TM or HALT_TM (the acceptance and halting problems for TMs). Call it U.
2) Show that U is reducible to L.

How do we do this? There are two ways:
1) By a Turing reduction: A < B.
a) Assume there is a decider for B, let's call it R.
b) construct input to R based on the input to S. We want a direct correspondence between R's decision and S's decision.
c) S halts on all inputs.

2) By a map reduction (A <m B).
a) give a computable function f (whose input is a member of A, and output is a member of B) which maintains for all input w - if (and only if) w is in A, then f(w) is in B.

That's it. Really study Reducibility - it will be emphasized on the final, and it's tough, so you really want to try and understand. Book examples and problems will help.

Thank You Alex for a fast reply. I'll make sure that I will chisel my notes on a stone tablet. I already ordered the stone tablet. jk

Thank you
Andy