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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community"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:
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.
=
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$