Here is the CFG (Context Free Grammar) for 0^n 1^n

S --> "" | 0S1

The start variable is S, and it can be replaced by the empty string or
OS1.

Here is how to derive 000111:

S 0S1 00S11 000S111 000111

Make sure you can draw the parse tree for this.


Here is the CFG for arithmetic expressions that Java uses

E --> E+T | E-T | T
T --> T*F | T/F | F
F --> (E) | i

Where E is the start variable and i is any numerical constant or
identifier: 1, 2, x, y, ...

Here is how to derive 2*(3+4)-5

E E-T E*F-T F*F-T 2*F-T 2*(E)-T 2*(E+T)-T 2*(T+T)-T 2*(F+T)-T
2*(3+T)-T 2*(3+F)-T 2*(3+4)-T 2*(3+4)-F 2*(3+4)-5


Here is a PDA for 0^n 1^n

s0 --> 0s	// if you see a 0, push it
s --> a		// switch to matching state
0a1 --> a	// if you see a 1, you can pop a 0
a is accepting on empty stack and input

Here is this PDA running on 000111:

s000111 0s00111 00s0111 000s111 000a111 00a11 0a1 a

If the input and stack are both empty and it's in an accepting state,
the input wins.


Here is how to convert a CFG into a PDA.  Let's convert the CFG for
0^n 1^n into a PDA.

s --> Sp	// push the start variable
Sp --> p[0S1]	// pop S and push the reverse of 0S1, eventually
		// p[0S1] is a special state that pushes the
		// reverse of 0S1, eventually
		// Why OS1?  Because there is a rule S --> OS1
p[0S1] --> 1p[0S]	// to push the reverse of OS1, push 1
			// and then push the reverse of OS
p[0S] --> Sp[0]	// to push the reverse of OS, push S and
p[0] --> 0p	// push (the reverse of) O
Sp --> p	// This follows from the rule S --> ""
0p0 --> p	// if you see a 0, you can pop a 0
1p1 --> p	// if you see a 1, you can pop a 1
p is accepting

So the states are:

s	start
p	accept (if both stack and input are empty)
p[0]	push (the reverse of) 0 on the stack
p[0S]	push the reverse of 0S on the stack
p[0S1]	push the reverse of OS1 on the stack

Don't be confused by the state named ``p[0S1]''.  I could have called
it ``a'', but then you would have to remember what ``a'' means: push
the reverse of 0S1, eventually.

Let's run the PDA on 000111:

s000111 Sp000111
p[0S1]000111 1p[0S]000111 1Sp[0]000111 1S0p000111 1Sp00111
1p[0S1]00111 11p[0S]00111 11Sp[0]00111 11S0p00111 11Sp0111
11p[0S1]0111 111p[0S]0111 111Sp[0]0111 111S0p0111 111Sp111
111p111 11p11 1p1 p


In general, the PDA is

s --> Sp	// push the start variable
Ap --> p[BCD]	// if A --> BCD is a rule
p[BCD] --> Dp[BC]	// implement p[BCD]
p[BC] --> Cp[B]		// using extra states
p[B] --> Bp		// p[BC] and p[B]
xpx --> p	// if you see terminal x, you can pop the same x off the stack


Here is how to convert a PDA into a CFG.

First of all, the PDA cannot have states which simultaneously pop and
push.  Suppose there is such a state:

apb --> cq	// In state p, pop a, read b, and push c

Add an extra state ``q[c]'' which means ``push c and switch to q'':

apb --> q[c]
q[c] --> cq

Now we can convert the PDA to a CFG.  The CFG has variables of the
form ``S[p,q]'' where p and q are states of the PDA.  The variable
``S[p,q]'' means the set of strings which the PDA can start reading in
state p with an empty stack and which can take the PDA to state q with
an empty stack.

So if S[p,q] can generate w, then the PDA can do the following

pw	// start like this
q	// end like this

Let s be the PDA starting state.  For each accepting state ``a'',
we add the rule

S --> S[s,a]		// rule 1

In other words, the start variable S generates all strings that take
the PDA from the start state to an accepting state on an empty stack.

For each PDA rule that neither pushs nor pops

pa --> q	// read a (can be "") and switch from state p to state q

add the grammar rule

S[p,q] --> a		// rule 2

For each pair of rules that push and pop the same symbol b

pa --> bq	// read a, push b, switch from p to q
brc --> t	// pop b, read c, switch from r to t

add the grammar rule

S[p,t] --> a S[q,r] c	// rule 3

Finally, for each set of three states p,q,r add the grammar rule

S[p,q] --> S[p,r]S[r,q]	// rule 4

O.K., let's apply these to the DFA for O^n 1^n:

s0 --> 0s
s --> a
0a1 --> a

S --> S[s,a]			// rule 1
S[s,a] --> ""			// rule 2 based on s --> a
S[s,a] --> 0 S[s,a] 1		// rule 3 based on s0 --> 0s and 0a1 --> a
S[s,a] --> S[s,s] S[s,a]	// rule 4
S[s,a] --> S[s,a] S[a,a]	// rule 4
S[s,s] --> S[s,s] S[s,s]	// rule 4
S[s,s] --> S[s,a] S[a,s]	// rule 4
S[a,s] --> S[a,s] S[s,s]	// rule 4
S[a,s] --> S[a,a] S[a,s]	// rule 4
S[a,a] --> S[a,s] S[s,a]	// rule 4
S[a,a] --> S[a,a] S[a,a]	// rule 4

We can throw away all the rule 4 rules because they all generate
either S[s,s], S[a,a], or S[s,a], and we have no rule 2 or rule 3
rules to get rid of these.