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?
$\begingroup$
$\endgroup$
8
-
1$\begingroup$ It seems like you have a pretty solid proof (might need some polishing, though). Is there an actual question here? $\endgroup$– RaphaelCommented Feb 10, 2014 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$– babouCommented Feb 10, 2014 at 12:12
-
$\begingroup$ So, if my reasoning is correct, just answer yes XD $\endgroup$– asdfCommented Feb 10, 2014 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$– RaphaelCommented Feb 10, 2014 at 12:33
-
$\begingroup$ It seems Raphael's answer means yes, and I do answer that too. You are right $\endgroup$– babouCommented Feb 10, 2014 at 12:57
|
Show 3 more comments