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$
$\endgroup$
7
1 Answer
$\begingroup$
$\endgroup$
2
"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.
answered Feb 15, 2015 at 15:29
-
$\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$ Feb 15, 2015 at 17:08
-
$\begingroup$ @Mahesha999 Sorry, misread stack for input. I will delete my PS. $\endgroup$ Feb 15, 2015 at 18:58
=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$