1
$\begingroup$

I am trying to create a DPDA that accepts words from the following Language:

$$ L = \{wx \; | \;w \in \{a,b\}^*, \#a = \#b \} $$

My intuition was to initially put an $x$ on the stack and then write an unlimited amount of $a$ or $b$, while both operations put an $B$ or $A$ on the stack. Then, in the second last state we can write an limited amount of $a$ and $b$ for popping an $A$ or $B$ from the stack.This ensures that the amount of $a$ and $b$ are equal before we can read the initial $x$ from the stack. As a last step, we read $x$ as the last element of the stack. However, building this determinstic seems too complex. Any hints?

$\endgroup$
2
  • $\begingroup$ Is $x$ a string in $\{a, b\}^*$ or a single letter? If the latter, the PDA is really simple. $\endgroup$ Jun 11 at 14:49
  • $\begingroup$ a single letter. $\endgroup$
    – dnr
    Jun 11 at 15:57
1
$\begingroup$

You have to keep track of $\#a - \#b$ at each point of the input. This number can become negative, so say the number of excess $a$ is represented by that many $A$ on the stack, and the number of excess $b$ by $B$s. If at the end of the string there is no excess (empty stack), accept.

Details of the construction are left to the gentle reader.

$\endgroup$
1
$\begingroup$

Reading a $a$ and a $b$ should "compensate" each other. For example, reading a $a$ could push a $A$ or remove a $B$ depending on the stack, and conversely when reading a $b$.

You can then accept when the stack is empty (or contains the initial symbol).

$\endgroup$
2
  • $\begingroup$ but if they only compensate each other, and let's say $b$ pushes $A$ on the stack and $a$ pops that $A$, I would not be able to read $baaaaabbbb$. If that is was your suggestion. $\endgroup$
    – dnr
    Jun 11 at 13:54
  • $\begingroup$ Your proposition is not very logical and is not what I proposed. When reading $baaaaabbbb$, what I propose is push a $B$, then remove a $B$, then push a $A$ four times, then remove a $A$ four times. That's why I added "depending on the stack". $\endgroup$
    – Nathaniel
    Jun 11 at 13:58

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.