Scribe  Sean McBride
 Editor 
 Editor 
Notes from Friday, October 15
Grammar Review
0^{n}1^{n} 
Balanced Parens 
{ w  w {a,b}* and w contains the same # of a's and b's } 
S > 'empty' 
pset > 'empty' 
E > 'empty' 
S > 0S1 
pset > (pset) 
E > aEb  bEa 

pset > pset pset 
E > EE 
 You should be able to write grammar rules without using stars or sub/superscripts.
 BNF notation often uses stars, but a formal contextfree grammar doesn't need/usually have them.
Grammar Ingredients
 Start Symbol (nonterminal)
 Set of Nonterminals
 Set of Terminals
Rules: nonterminal > concatenated terminals and nonterminals
PushDown Automata
PDA's : contextfree grammars :: FSA's : regular expressions
A PDA is a way to represent the same thing that a contextfree grammar represents, in the same way that a FSA and a regular expression represent the same thing. PDA's and contextfree grammars both deal with languages that have an associated "parse tree," or a memory of where they have been before. Thus, you can describe things with PDA's / CFG's that you couldn't describe with FSA's / RE's due to the pumping lemma.
At a basic level, a PDA is an FSA with a stack tacked on. On each transition, the conditions can also have to do with what is on the top of the stack as well as the input string and the current state, and the result can include an action on the stack (push, pop, replace) as well as the usual change in state.
Formal Notation
< Q(States), Sigma(Alphabet), ?(Stack Alphabet), Delta(Transition Table), Q0(Start State), S(Start Symbol on Stack), F(Set of Accepting States) >
In addition, the transition table is slightly different. Each transition consists of:
q(Current State), a(Input Symbol), s(Top of Stack) > q'(New State), st(New Stack Top)
Operations done to the stack during a transition:
Example Operation 
Notation (s>st) 
Push 0 (regardless of current top) 
epsilon>0 
Push 0 (only if 1 on top) 
1 > 10 
Replace 1 with 0 
1 > 0 
Pop top 0 off 
0>epsilon 
etc. 

I can't draw a PDA here, but they look just like an FSM, but with a different notation on the transitions. Instead of something like "a" which means "on input a, take this transition," the transitions look like "a, 0>01" which means "if input a and 0 on top of stack, take transition and push 1 on top of the 0."
One common convention in PDA's is to use a certain stack symbol to mean "end of stack". Many books use the dollar sign $ for this purpose.
Example PDA
This is the definition of the PDA for the grammar of 0^{n}1^{n} (some number of 0's followed by the same number of 1's):
< {q0, q1, q2, q3}, {0,1}, {$,0}, Delta(see below), {q0}, {none}, {q0, q3} >
Delta (the transition table) looks like this:
Start State 
Input 
Stack Top 
> 
New State 
New Stack Top 
q0 
epsilon 
epsilon (don't care) 

q1 
$ (add $ to top) 
q1 
0 
epsilon 

q1 
0 (add 0 to top) 
q1 
1 
0 

q2 
epsilon (pop a 0 off the top) 
q2 
1 
0 

q2 
epsilon (pop a 0 off the top) 
q2 
epsilon 
$ 

q3 
epsilon (pop a $ off the top) 
Any transitions that aren't in the table are implicitly transitions to the fail state.
Equivalence
PDA's and contextfree grammars can be transformed back and forth into each other just like FSA's and regular expressions. This is done in much the same manner: by simplifying/expanding the transitions and imploding/adding states. This is hard to talk about without a picture.