• For a fixed language L, know that there is a specific minimum number of states for any DFA recognizing L.
• Compute the suffix language L_q for each state q in a specific DFA.
• Mimimize a DFA by merging states with the same (suffix) language.

• Know the examples of non-regular languages given in lecture and Sipser.
• Tell whether a specific language L is regular. Examples of non-regular langauges will be like (but perhaps not identical to) those in lecture notes, section 1.4 in the book, homeworks.
• You won't be expected to know the pumping lemma for regular languages.
• You should be able to prove a given language L is not regular; you can do this using the direct proof (preferred) or use the pumping lemma.
• Use closure properties to prove that a language is not regular, given a "seed" language already known not to be regular.

• Formal definition of a context-free grammar (tuple notation).
• Define what it means for one string to yield or derive another string.
• Define what it means for a string w to be in the language of a grammar G.
• Design a context-free grammar that generates a specific language L.
• Describe the language generated by a specific grammar G.
• Draw a parse tree for a word w using a grammar G.
• Give a derivation of a word w using a grammar G.
• Know that a single string may have more than one distinct parse trees. Produce examples illustrating this phenomenon.
• Algorithms on CFGs: deciding whether a language is empty, etc.

• Define Chomsky normal form.
• Recognize whether a grammar is in this form.
• You won't be tested on doing the conversion from CFGs to Chomsky Normal Form.
• The CYK algorithm for membership of a word in the language of a CFG in Chomsky Normal Form.

• Definition of recursive automata, syntax and tuple notation.
• Know the formal definition of acceptance of words using configurations that involve both state and stack.
• Know how to specify a recursive automaton using tuple notation and state diagrams, and convert between the two notations.
• Construct a recursive automaton to recognize some specific language L.
• Describe the language recognized by a given RA.
• Know how to transform RAs to another RA in order to accept a different language; in particular, closure constructions on RAs.
• Know that recursive automata are equivalent to context-free grammars. Know the conversion between RAs and CFGs, and know how to do it on particular examples.

• Closure properties of CFLs-- closure under union, concatenation, *, homomorphism, closure under intersection with a regular language, etc.
• Know that CFLs are not closed under intersection and complementation.
• For languages that strongly resemble examples covered in class and/or in the text (e.g. section 2.3), be able to tell whether a specific language L is context-free.
• Use closure properties to prove that a language is not context-free, based on the fact that some other "seed" language is not context-free.
• Know the pumping lemma statement for context-free languages; should be able to understand and demonstrate it for sample CFLs.
• You will not be asked to prove any particular language is not context-free using the pumping lemma.

• You should be able to prove various questions about automata, CFGs and RAs in general. There is no fixed set of facts you should know what to prove--- questions on proofs can be on any of the above topics, and you should be able to demostrate clear thinking, prove things precisely, using suitable mathematical notation.

This exam will not ask questions about Turing machines.