0
$\begingroup$

looking for old tests of Language Theory, I see this exercise:

Give a PDA automata that recognize the language $L = \{w \in \{a,b\}^*,\ 2|w|_a=3|w|_b\}$

They propose this solution: PDA Automata

Can anyone help me to understand what strategy they used?

Sorry for my english, is not my native language.

Thanks.

$\endgroup$
1
$\begingroup$

The idea of this PDA is very simple. Start with a PDA for $L' = \{ w \in \{a,b\}^* : |w|_a = |w|_b \}$, and now modify it as follows:

  1. Whenever you read $a$, simulate the original PDA reading $aa$.
  2. Whenever you read $b$, simulate the original PDA reading $bbb$.

Hopefully you can see why the new PDA accepts $L$ given that the original one accepted $L'$.

The PDA for $L'$ maintains a stack which can be of three different types, depending on the word $x$ seen so far:

  1. If $|x|_a = |x|_b$ then the stack contents is $Z_0$. In particular, this is also the initial stack.
  2. If $|x|_a > |x|_b$ then the stack contents is $B^{|x|_a - |x|_b} Z_0$.
  3. If $|x|_a < |x|_b$ then the stack contents is $A^{|x|_b - |x|_a} Z_0$.

When the top-of-stack is $Z_0$ we know that $|x|_a = |x|_b$, and so we optionally move to the final state; the PDA will accept only if $x = w$, since otherwise it will get stuck.

When converting this PDA to the one for $L$, we use epsilon transitions to simulate reading the second $a$ and the second and third $b$s.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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