We know algorithm to convert each PDA in the underlying grammar that generates the language the PDA recognize. But we have also the algorithm for creating a two state pda from a grammar. This algorithm use the first state for all the computation, with rules based on the stack and the input symbol, and when the stack is empty goes to a final state. This means that, for all the generic PDAs we can create a minimal PDA with only two states (and a lot of rules for the first state). Am I right?

  • 1
    $\begingroup$ It seems like you have a pretty solid proof (might need some polishing, though). Is there an actual question here? $\endgroup$ – Raphael Feb 10 '14 at 11:41
  • $\begingroup$ @Raphael You seem to be contradicting yourself, You put it on hold as unclear what is being asked, and you also answer his question which is only whether his reasonning is correct (and implicitly if there is more to the topic, I guess). $\endgroup$ – babou Feb 10 '14 at 12:12
  • $\begingroup$ So, if my reasoning is correct, just answer yes XD $\endgroup$ – asdf Feb 10 '14 at 12:23
  • 2
    $\begingroup$ It may seem inconsistent but it's not; it's only that the closing reasons are not as specific as you'd like. There is no "real" question here, as in one that admits a "real" answer (in particular more than "yes" or "no"). See here for a related discussion. (cc @babou) $\endgroup$ – Raphael Feb 10 '14 at 12:33
  • $\begingroup$ It seems Raphael's answer means yes, and I do answer that too. You are right $\endgroup$ – babou Feb 10 '14 at 12:57