I believe that the following NPDA accepts the language $$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$ where $n_a(w)$ represents number of symbol $a$'s in string $w$.


Is there a two-state NPDA that accepts the same language?

  • $\begingroup$ I removed part 2 of your question, since you weren't asking anything more than "Is my answer correct?" That kind of question isn't well-suited to Stack Exchange because the only available answers are just "yes" or "no", which isn't much use to you or anyone else who might visit the site in the future. (See related meta discussions here and here.) $\endgroup$ Commented Feb 15, 2015 at 13:29
  • $\begingroup$ Thanks @DavidRicherby, I know this question is not well suited for stackexchange. I could have coined this question as how can I prepare npda for... and then I guess it would have become suitable for posting as the answer will not be mere yes and no and also somewhat more challenging. But now just adding my effort made it unsuitable for posting. I sometimes believe despite of awesome effort of community to keep content worth, whether question/answer is worth or not is very dependent on perception, situation, word usage... $\endgroup$
    – Mahesha999
    Commented Feb 15, 2015 at 13:37
  • $\begingroup$ Also those two languages were different in their signs: = vs >=. So better keep both of the languages problems. So I wanted to know whether my npdas were correct and also if any other npdas are possible for both of them possibly with lesser states. $\endgroup$
    – Mahesha999
    Commented Feb 15, 2015 at 13:39
  • $\begingroup$ I agree that there is a balance between providing enough of an answer to avoid being closed as a problem dump and not providing so much that it's just a check-my-answer. Fundamentally, though, this just proves the point: if there's no way of asking the question in a way that makes it suitable for the site, then the question just isn't suitable for the site. "Is there a 2-state NPDA equivalent to this 3-state one?" at least has some scope for answers that aren't just "get more practice making NPDAs" so I think it's a decent question. $\endgroup$ Commented Feb 15, 2015 at 13:41
  • 1
    $\begingroup$ It's unlikely that anyone else will come along wondering if exactly the same solution attempt to the question is correct. $\endgroup$ Commented Feb 15, 2015 at 13:49

1 Answer 1


"Is there a two-state NPDA that accepts the same language?"

Yes, every PDA can be replaced by one that has two states, one accepting and one non-accepting. In general one uses three steps to prove this formally:

  • Every PDA (with empty stack acceptance) can be transformed into a CFG. The construction is sometimes known as the triplet construction: a single nonterminal of the CFG codes two states and a stack symbol of the PDA.
  • Every CFG can be transformed into a PDA with a single state and empty stack acceptance. That equivalence is quite straghtforward.
  • PDA with empty stack acceptance are equivalent to PDA with final state acceptance. But, where the stack-PDA may have a single state, the state-PDA usually uses one more, for acceptance.

Always, when discussing PDA, be explicit on the acceptance mode. (But that might be a silly request when your textbook considers only one of these types.)

PS. By the way, your machine seems to have the basic counting ideas implemented.

  • $\begingroup$ Stack:[$z_o$]; In:<b>, $\{b,z_o,bz_o\} \rightarrow$ [$z_o,b$]; <a>, $\{a,b,\epsilon\} \rightarrow$, [$z_o$]; <a>, $\{a,z_o,az_o\} \rightarrow$ [$z_o,a$], so finally there will be {$\epsilon,a$,} for which there is no transition out of 1st state. In short $q_o,baa,z_o$ ⊢ $q_o,aa,bz_o$ ⊢ $q_o,a,z_o$ ⊢ $q_o,\epsilon,az_o$ $\endgroup$
    – Mahesha999
    Commented Feb 15, 2015 at 17:08
  • $\begingroup$ @Mahesha999 Sorry, misread stack for input. I will delete my PS. $\endgroup$ Commented Feb 15, 2015 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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