0
$\begingroup$

$L=\{w \mid w \in \{a,b\}^*$, $\text{the number of a's is at least the number of b's} \}$

I'm stuck trying to build an NPDA that accepts $L$.

$\endgroup$
1
$\begingroup$

You need to design a NPDA that behaves as follows:

  • If it reads "a" and stack is empty push "a" onto stack
  • If it reads "b" and stack is empty push "b" onto stack
  • If it reads "a" and top entry on stack is "a" the push "a" onto stack
  • If it reads "b" and top entry on stack is "a" the pop "a" from the stack
  • If it reads "a" and top entry on stack is "b" the pop "b" from the stack
  • If it reads "b" and top entry on stack is "b" the push "b" onto stack

The top entry on the stack is therefore "a" if the NPDA has read more "a"s than "b"s, and is "b" if it has read more "b"s than "a"s. If the stack is empty then the NPDA has read equal numbers of "a"s and "b"s.

The accepting states are therefore if the top entry of the stack is "a" or the stack is empty.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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