Scribe - Sean McBride
Editor -
Editor -

Notes from Friday, October 15

Grammar Review

0ⁿ1ⁿ	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 context-free grammar doesn't need/usually have them.

Grammar Ingredients

Start Symbol (nonterminal)
Set of Nonterminals
Set of Terminals
Rules: nonterminal -> concatenated terminals and nonterminals

Push-Down Automata

PDA's : context-free grammars :: FSA's : regular expressions

A PDA is a way to represent the same thing that a context-free grammar represents, in the same way that a FSA and a regular expression represent the same thing. PDA's and context-free 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ⁿ1ⁿ (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 context-free 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.