Pushdown Automaton accept all words belong to language over (a,b) where the first letter 'a' has half of the occurences of the second letter 'b'. Can someone help me with a JFLAP like digram of this Automaton?

  • 2
    $\begingroup$ This seems like your homework assignment. Nobody likes to do your home work for you. If you have any doubts or need clarifications, we are more than happy to help. $\endgroup$
    – codeR
    Commented May 10 at 13:56
  • $\begingroup$ Hint: for each 'a', you need to match two 'b's. If 'a' = +2 (credit) and 'b' = -1 (debit), at the end, your balance should be exactly $0$. $\endgroup$
    – codeR
    Commented May 10 at 14:00
  • $\begingroup$ Thank you. Yeh I had some challenges and was looking for some directions as to how this can be solved. $\endgroup$
    – Vunag
    Commented May 11 at 14:55
  • $\begingroup$ Does this answer your question? Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$ $\endgroup$ Commented May 11 at 21:06
  • $\begingroup$ Yes, @Hendrik it does but I think that the solution there is less clear then what suggested below. Thank you $\endgroup$
    – Vunag
    Commented May 13 at 10:20

2 Answers 2


My Solution Does anyone have any comments about the solution?


It represent the language {a^nb^2n} like abb,aabbbb,... let take an example abb you are pussing two a's for every 'a' you see, into stack and popping them by matching with b's

  • $\begingroup$ I am not sure it is the same. In this case what is needed is that every word in every order of a and b with only one condition that number of a's will be half the number of b's. For example the word abbbabbba is in the language. Can you say if the solution I suggested is the correct solution? $\endgroup$
    – Vunag
    Commented May 11 at 16:41
  • $\begingroup$ This answer is incorrect. The suggested PDA refuses $\mathsf{bab}$ which should be accepted. $\endgroup$
    – Kai
    Commented May 13 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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