The second exam will focus on context-free languages (CFLs). Of course, all regular languages are also context-free, but not all context-free languages are regular. In addition to general familiarity with context-free languages, context-free grammars (CFGs), and pushdown automata (PDAs), you should be prepared for the following:
- answer true/false and multiple choice questions about context-free languages (CFLs), context-free grammars (CFGs), and pushdown automata (PDAs),
- read and understand the formal notation used for the definitions of CFGs and PDAs,
- prove that a language (given in set builder notation) is context-free by constructing a CFG to generate it,
- given a CFG, produce a derivation or derivations of a string or strings in the language of the grammar,
- prove that a CFG is ambiguous by providing two leftmost derivations of the same string,
- identify strings that are or are not in the language of some CFG or PDA,
- recognize whether a grammar is in Chomsky normal form or not (you will not be asked to convert a grammar to ChNF)---that is, identify which rules in a context-free grammar violate the constraints of ChNF,
- read transition labels including stack operations in a PDA,
- convert an arbitrary DFA (given a formal definition or state diagram) to an equivalent CFG,
- trace execution on a small PDA (one or two steps at most), and
- complete a short proof that some language is non-regular by application of the pumping lemma for regular languages.