PDA for language where order of letters does not count

Question

L = {w | 2|w|a != 3|w|b + 2} ∪ {aaab, bbba}. |w|a = number of a's, same for b.

How do I use the top of the stack when only the number of a's/b's counts and they can be in any order?

Answer 1

It is not completely clear what you mean by "use the top of the stack."

To construct a PDA may start with one for the language {w: |w|a = |w|b}.

When it reads an a it

• puts an a on the stack if there is already an a or the stack is empty
• removes a b from the stack

For the case of reading a b symmetrically. The PDA accepts if the stack is empty when the entire input has been read. So the stack indicates whether so far more a or more b have been read, because the majority symbol is the one that it contains.

With the factors 2 and 3 and the added 2 b it becomes a bit more complicated. I would not handle this in the stack but in the states. This means, we implement a counter for 0 or 1 a and for 0,1 or 2 b there. When we read a an input symbol x, we first try to increment the respective counter in the state. If this is possible, this is the only thing we do. If the counter is full, we set it to zero and take the action corresponding to this symbol in the PDA above for the stack.

For the +2, we count the first two b in the states before we actually start filling the counter.