Problem $3$

Recall that the following PDA recognizes $\{0^($n$)1^($n$)|$n$>=0\}.$

First, simplify this PDA so that it $(1)$ has a single accept state, $(2)$ empties its stack before accepting an

input string, and $(3)$ has transitions that either pop a symbol from the stack or push a symbol onto the stack.

Show the resulting PDA's state diagram. Then consider converting this simplified PDA to an equivalent

CFG$.$ Since there are many, many rules in this equivalent CFG$,$ list only the rules $(1)$ with the start variable

on their left$-$hand sides and $(2)$ of the form A$\_($p$\_($i$)$p$\_($j$))->$aA$\_($p$\_($k$)$p$\_($l$))$b$.$