Context-free grammars (CFG)
definition, terminals, non-terminals & goal or start symbol S,
productions; derivations, working string; BNF;
parse and derivation trees, ambiguous CFG; total language tree

Regular grammars
generating CFG from FA, regular langs. are CFLs; semi-word,
"regular grammar" (not just any grammar for a regular lang.)

Chomsky normal form (CNF)
lambda-productions, nullables, unit-productions, groups on right
must be all non-terminals; non-terminal pairs; left-most deriv.

Pushdown automata (PDA)
looking for CFG machine; input tape, blank letter; START state,
halt states (ACCEPT, REJECT), READ states, FA equivalence;
stack, PUSH, POP, non-determinism; PDA definition

CFG = PDA
converting CFG in CNF to PDA: push S, single POP with loops
for each live and dead production, READ blank, ACCEPT;
PDA to CFG: conversion form, summary table; row language,
3 cases of productions ( S, no PUSH, with PUSH; + Row->char),
joint and stack consistency; string language productions ^

Non-context-free languages
live/dead productions; derivation of long word requires sub-tree
with self-embedded non-terminal; pumping lemma for CFLs

Context-free languages
operations producing CFLs: union, set product, Kleene closure;
proofs, danger of machine proof
intersection and complement may or may not be CFL; special cases:
DPDAs that always stop, intersection with RL

Decidability
undecidables; decidables: empty, finite, word membership;
useful non-terminals; CYK algorithm
parsing: definition, relevance; top-down, left-most subst.,
breadth vs. depth, pruning, back-tracking;
bottom-up, pruning; compilers