# Constructing PDA for $L = \{w\in\{a,b\}^{\ast}\;|\; |w|_a > 2|w|_b\}$

Construct a PDA, which recognizes the following language $$L$$: $$L = \{w\;|\; |w|_a > 2|w|_b\}$$, so it is the language that consists of words which have more than twice as many $$a$$'s as $$b$$'s.

I have constructed a PDA, which I believe to recognize $$L$$, however it is too complicated to prove its correctness. Is there an easy way to construct such an automata? I need a hint.

• Take a look at automata accepting identical numbers, then $|w|_a > |w|_b$ and $|w|_a = |w|_b = 2n, n \in \mathbb N$. Nov 2, 2021 at 5:31

While reading prefixes $$u$$ of a word $$w$$, you need to count $$|u|_a - 2|u|_b$$ and check whether this value is greater or equal to $$1$$ when $$u = w$$.

Counting only the value of $$|u|_a$$ is easy: when you read a $$a$$, push a $$A$$ in the stack. The number of $$A$$ in the stack will be the same as $$|w|_a$$ at the end.

Counting only the value of $$-2|u|_b$$ can be done with the same idea: when you read a $$b$$, push two $$B$$'s in the stack.

However, if you need to do both, it could be a bit trickier than that. You could still combine the ideas:

• if there is nothing or a $$A$$ at the top of the stack while reading a $$a$$, then push one more $$A$$ in the stack;
• if there is nothing or a $$B$$ at the top of the stack while reading a $$b$$, then push two more $$B$$'s in the stack;

Can you find what to do if there is a $$A$$ at the top while reading a $$b$$, or a $$B$$ while reading a $$a$$? I will edit my answer if you need more details.

• I think that we should somehow transform sequence in stack into equivalent one, but more simple, for example if we have $aaba$ then after reading first two letters there are two $a$'s in stack but after adding $b$ (which is equivalent to adding $-2$) we can substitute these two $a$'s by $\varepsilon$. But I don't get why we should push two more A's in the stack in your first case, shouldn't it be the other way round? Nov 2, 2021 at 12:08
• Yeah, my mistake. Nov 2, 2021 at 14:03
• @Egor Consider accepting the answer if it helped you. Nov 28, 2022 at 8:11