Pushdown Automata for $L = \{ w \in \{a,b\}^* | \#_b{(w)} = 2\#_a{(w)} \}$

Question

Pushdown Automata for $L = \{ w \in \{a,b\}^* | \#_b{(w)} = 2\#_a{(w)} \}$.

This is what I've tried so far and it fails for some inputs, like for example $babbab$, fails for every input that has $b^{2i}a^{i}$ for $i \ge 1$

Answer 1

There seem to be three conditions, which would be better represented as (groups of) states:

• Too many $a$s so far,
• too many $b$s so far, and
• exactly twice as many $b$s as $a$s.

Then the stack keeps track of how many excess $a$s or $b$s there are and possibly if we have an unpaired $b$ right now. In each cloud, there should be a little machine for inspecting the top segment of the stack (without consuming input) that determines whether the top segment indicates that we have accumulated two $b$s and an $a$ that are uncancelled.

On the excess $a$s side, the stack should always look like [data about uncancelled $b$s -- at most 1][count of uncancelled $a$s]. On the excess $b$s side, the stack should always look like [count of uncancelled $b$s]. When we pass through exactly twice as many $b$s as $a$s, we should be in an accepting state and have an empty stack. Note that this means a transition from excess $b$s to excess $a$s, when we have one $b$ pending and receive an $a$ as input, which will require swapping the stack around.

It can be instructive to go an entirely different way: Start with an FSA that consumes three input symbols and ends in one of four states, indicating how many $a$s and $b$s were seen, then from each of those states, pass through a PDA step which inspects the top of the stack to see if any additional cancellation with prior symbols can occur.

As an aside: If I were tracking excess $a$s or $b$s on the stack, I would just store $A$s and $B$s there (or, depending on my audience, $a$s and $b$s).