An exercise that asks for informal description of the language accepted by a specific PDA

Question

This is a problem that I have found from Introduction to automata theory, languages and computation by John Hopcroft and Jeffrey Ullman. PDA P=({q0, q1, q2, q3, f)}, {a, b}, {Z0, A, B}, δ, q0, Z, {f}) has the following rules defining δ:

δ(q0,a,Z)=(q1,AAZ)       
δ(q0,b,Z)=(q2,BZ)            
δ(q0,∈,Z)=(f,∈)

δ(q1,a,A)=(q1,AAA)         
δ(q1,b,A)=(q1,∈)                        
δ(q1,∈,Z)=(q0,Z)

δ(q2,a,B)=(q3,∈)               
δ(q2,b,B)=(q2,BB)                   
δ(q2,∈,Z)=(q0,Z)
  
δ(q3,∈,B)=(q2,∈)            
δ(q3,∈,Z0)=(q1,AZ)

Note that since each of the sets above has only one choice of move, we have omitted the set brackets from each of the rules.

It has been asked to informally describe L(P). After observing, it seems to me that in case the string started with a, no prefix should contain more b's than twice the number of a's and in the string, number of a's * 2 = number of b's. Am I wrong about this particular description? How can I informally describe the language that the PDA accepts?

Answer 1

The language of this PDA seems to be the set of all strings that have twice as many $b$'s as $a$'s.

If there is a deficit of $a$'s in the prefix seen so far in the sense that the number of $b$'s exceeds twice the number of $a$'s, then the PDA would be operating essentially from state $q_2$, where it would modify the number of $B$'s on the stack. In this state, the PDA would remove two $B$'s for each $a$ it sees in the input and push a $B$ for each $b$ it sees in the input.

If there is a deficit of $b$'s in the prefix seen so far in the sense that number of $b$'s is less than twice the number of $a$'s, then the PDA would be operating essentially out of state $q_1$, where it would work with the $A$'s that are on the stack: for each $a$ in the input, push two $A$'s onto the stack, and for each $b$ in the input, remove an $A$ from the stack.

Thus, at any given time, the stack contains either all $A$'s or all $B$'s depending on which way the deficit is. The machine needs to deal with these two situations differently: if there is a surplus of $B$'s, then the next input $a$ causes two $B$'s to be popped from the stack, whereas if there is a surplus of $A$'s, the the next input $a$ causes two more $A$'s to be pushed onto the stack.

When the deficit swings from one way to another, the machine transitions from $q_2$ to $q_1$ (via $q_3$) or from $q_1$ to $q_2$ (via $q_0$).