0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – giochi
    Nov 2, 2021 at 12:08
  • $\begingroup$ Yeah, my mistake. $\endgroup$
    – Nathaniel
    Nov 2, 2021 at 14:03
  • $\begingroup$ @Egor Consider accepting the answer if it helped you. $\endgroup$
    – Nathaniel
    Nov 28, 2022 at 8:11

Your Answer

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

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