Understanding PDA and Equivalence of PDA and CFG

Question

When we wanted to construct a PDA for $0^n1^n$ the idea was to put all the zeroes (which is a part of the input string) to the stack associated with the PDA, and then pop each of them when we get a $1$ from the latter part of the input.

But when we try to prove that, we can create a PDA for a given CFG we put nonterminals and terminals in the stack and try to match it with input and pop from the stack.

Why do we do something like this? For a problem, we push some part of my input to the stack and match rest of them, and for some problems do not push any input symbol rather only use inputs to compare?

Maybe I am missing some intuitive part of it.

Answer 1

Your question is, in essence,

Why does the proof that every context-free grammar can be converted to an equivalent PDA proceed in a particular way rather than in another way?

It's hard to answer such a question unless it gets more specific. For example, you can ask why the resulting PDA have to invoke nondeterminism. The answer is that some context-free languages cannot be accepted by a DPDA. Indeed, while this particular proof uses PDAs acting in a certain way, another proof might use PDAs acting in a different way.

One alternative such proof uses the Chomsky–Schützenberger representation theorem. The theorem states that every context-free language can be realized as $$ h(D \cap R), $$ where $D$ is a Dyck language (the language of all correctly nested strings of parentheses of some fixed number of sorts), $R$ is a regular language, and $h$ is a homomorphism. This theorem, which can be proved directly using context-free grammars (see, for example, Context-free languages and pushdown automata by Autebert, Berstel and Boasson, from the Handbook of Formal Languages), allows to convert a context-free grammar to a PDA which is more like the one for $0^n 1^n$, along the following lines:

1. Start with a PDA for $D$. This is a PDA that pushes whenever encountering a left parenthesis, and pops whenever encountering a right parenthesis (checking that the two parentheses, the one on the stack and the one being read, have the same type).
2. Construct a DFA/NFA for $R$, and use the product construction to construct a PDA for $D \cap R$.
3. Construct a PDA for $h(D \cap R)$ by replacing each transition on $\sigma$ to a transition on $h(\sigma)$.

If you apply this construction to $0^n1^n$ (which you can realize as $D \cap 0^*1^*$, where $D$ is the Dyck language with a single type of left parenthesis $0$ and the corresponding right parenthesis $1$) then you get a PDA which is remarkably similar to the one you describe.

Answer 2

That,

we can create a PDA for a given CFG