# Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?

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%.

• Are you certain that the language is context-free? Have you tried proving the opposite?
– Raphael
Mar 17, 2016 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).