1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "But when we try to prove that" -- what dod you want to prove? $\endgroup$ – Raphael Jan 12 '18 at 11:35
  • $\begingroup$ I have a hard time telling what your question is. Are you asking why some PDAs use different techniques than others, or are you asking why certain PDAs and CFGs are equivalent? $\endgroup$ – Raphael Jan 12 '18 at 11:35
  • $\begingroup$ That, we can create a PDA for a given CFG $\endgroup$ – Rayhan Rashed Jan 12 '18 at 11:39
  • $\begingroup$ I am asking what is the difference between the stack use in proving CFG-PDA equivalence and generating PDA for an arbitrary language. $\endgroup$ – Rayhan Rashed Jan 12 '18 at 12:39
  • $\begingroup$ equivalence means you have to be able to convert both ways. $\endgroup$ – ratchet freak Jan 12 '18 at 13:19
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.