I am asked to construct a PDA to accept the language:

$\qquad \{w \in \{0, 1\}^* : \#_{0}(w) \ge \#_{1}(w)\}$

I am wondering how to interpret the $\#$ symbols and everything. Could someone please explain what exactly this means and how to construct it?

  • 2
    $\begingroup$ Your PDA must accept exactly those binary words where the number of zeros is at least the number of ones. $\endgroup$ – mrk Apr 4 '13 at 1:32
  • $\begingroup$ Oh so it means that the accepted string could be any random string of 0 and 1's as long as the number of 0's in the string is = or more than 1's $\endgroup$ – Matt Hintzke Apr 4 '13 at 1:34
  • 1
    $\begingroup$ yes. That's it. $\endgroup$ – mrk Apr 4 '13 at 1:43

This is pretty standard notation for

$\qquad \#_a(w) = |w|_a = $ number of occurrences of $a$ in $w$.

Building a PDA for this language is straight-forward. Find a hint below.

Use the stack to count $\#_0 - \#_1$ in the processed prefix of the input. Figure out how to model negative numbers.

| cite | improve this answer | |

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.