0
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Are you certain that the language is context-free? Have you tried proving the opposite? $\endgroup$
    – Raphael ♦
    Mar 17, 2016 at 8:25

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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