1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Are you trying to describe the PDA or the language that it accepts? The two are not the same. $\endgroup$ May 7 at 16:05
  • $\begingroup$ @YuvalFilmus I am trying to describe the language it accepts. $\endgroup$
    – swarna
    May 7 at 16:21
  • $\begingroup$ I think you're on the right track there must be twice as many $b$'s as $a$'s; however, I don't think this is required from a prefix of the input string. It's required only from the entire input string. $\endgroup$ May 8 at 13:34

1 Answer 1

1
$\begingroup$

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$).

$\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.