context free = left hand side is a single non-terminal
Parse trees apply to context free grammars
Context free are closed under union, concatenation, kleene star and (intersection with regular only) (NOT any intersection, complement)
Parse trees: Root S, branch through non terms to the leaves (terminal or e) (reading through the non leaves as node -> leaves-left-to-right should match a rule)
Pushdown automata - automata for context free languages (has a stack 'memory')
Pushdown automaton syntax: a (transition), 1 (test to compare to top of stack) : 1 (value to push to stack OR pop symbol)
Pushdown automata - will terminate as soon as there is a empty stack on a final state
