[FrontPage] [TitleIndex] [WordIndex

Notes from Friday, October 15

Grammar Review


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

Grammar Ingredients

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)


Push 0 (only if 1 on top)

1 -> 10

Replace 1 with 0

1 -> 0

Pop top 0 off



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 0n1n (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


Stack Top


New State

New Stack Top



epsilon (don't care)


$ (add $ to top)





0 (add 0 to top)





epsilon (pop a 0 off the top)





epsilon (pop a 0 off the top)





epsilon (pop a $ off the top)

Any transitions that aren't in the table are implicitly transitions to the fail state.


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.

2013-07-17 10:43