• 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 the number of states in a specific DFA.

• 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.
• State the pumping lemma for regular languages.
• Use the Pumping Lemma to prove that some language L is not regular.
• Use closure properties to prove that a language is not regular, given a "seed" language already known not to be regular. (See lecture 9.)

• Define 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, or a leftmost derivation, of a word w using a gramamr G.
• Know that a single string may have more than one (even a lot of) distinct parse trees. Produce examples illustrating this phenomenon. Interesting study question: can you write a grammar for which some string w has infinitely many distinct parse trees?

• Define Chomsky normal form.
• Recognize whether a grammar is in this form.
• Convert a grammar into Chomsky Normal form using the procedure from lecture 15.

• Know how to specify a PDA using tuple notation and state diagrams, and convert between the two notations.
• Know that PDA's are non-deterministic.
• Construct a PDA to recognize some specific language L. Use special bottom-of-stack symbol, exploit non-determinism ("guessing") when required.
• Describe the language recognized by some specific PDA.
• Create tuple notation for a new PDA, by modifying/combining components from existing PDAs. For example, give a PDA a single accept state, make it empty its stack before accepting, run a PDA and DFA in parallel to prove context-free languages are closed under intersection with regular languages.

• Know that PDA's are equivalent to context-free grammars. Sketch the algorithms for converting a PDA to a grammar and vice versa. Do the conversion (or parts of it) for concrete examples (e.g. convert a specific grammar into a PDA).
• 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.
• Know which basic operations (e.g. union, intersection with regular languages) the context-free languages are closed under.
• Give a high-level proof for each of these closure properties.
• Know which basic operations (e.g. intersection, taking subsets), the context-free languages are not closed under.
• 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. (See lecture 16.)

• Write a proof by induction on the length of derivations of strings defined by a grammar. (See homework 9 and lectures 14-15.)

This exam will not ask questions about Turing machines, nor about the context-free version of the pumping lemma.