2
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ Your PDA must accept exactly those binary words where the number of zeros is at least the number of ones. $\endgroup$
    – mrk
    Commented Apr 4, 2013 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$ Commented Apr 4, 2013 at 1:34
  • 1
    $\begingroup$ yes. That's it. $\endgroup$
    – mrk
    Commented Apr 4, 2013 at 1:43

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.