I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is >= 60% of symbol A.

I'm trying to think in terms of what to save on the stack. The problem of telling when there are 50% or more is trivial. You can just pop and push As and Bs on the stack to track which one has the majority. If an A is on the stack at the end, you're solid. however, in this problem we see that an A can be on the stack in the end and still not meet the criteria because it could be a ratio of 6 As to 5 Bs, which is under 60%.

  • 1
    $\begingroup$ Are you certain that the language is context-free? Have you tried proving the opposite? $\endgroup$ – Raphael Mar 17 '16 at 8:25

Assume you have to check whether $\#A \ge \frac 43\#B$, then this is equivalent to $3\#A \ge 4\#B$. This can be solved: just push 3 symbols for every $A$ and pop four of them for every $B$ (changing this a little when the number gets negative).

Adapt this to your fraction.


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.