# Constructing PDA for $a^{2n} b^{3n}$

So I have been given the task of creating an PDA that recognises the language

$\{a^{2n} b^{3n} \mid n = 0,1,2,\dots\}$.

Am I right in thinking that it needs to have at least 3 times number of $b$'s than $a$'s?

So for example: $aabbb$ would be accepted $aaabb$ would NOT be accepted However, how do I show that using JFlap because I am unfamiliar with the software?

• I don't understand what you want here. The statement you give is wrong. What do you want with a software? – Raphael Mar 10 '13 at 15:07
• @Raphael What do you mean by the statement is wrong? Have I considered the language incorrectly? Also I wish to create a PDA that would recognise the above mentioned language – Anish B Mar 10 '13 at 15:08
• There are not as many $b$'s as you claim. By the way, one simple way to get a PDA is build a grammar and convert it; there's a simple algorithm for the latter. – Raphael Mar 10 '13 at 22:21

The following pushdown automaton should do the trick. I publish this only because the existing answer can be improved upon. (Note, I am using $e$ to denote $\epsilon$- (or $\lambda$-) transitions. The idea is that the left-hand part counts the number of $a$'s (modulo 2). Each time it has seen two $a$'s, it pushes $3$ $b$'s onto the stack. Nondeterministically, the machine can change to the right-hand state. It then matches a $b$ from the string fro each $b$ on the stack.
Yes the number of b's is at least 3 times the number of a's except when n=0 in which case you get the empty string. Your language is equivalent to $\{(aa)^n(bbb)^n:n=0,1,\dots\}$. So if you can find a PDA for $\{a^nb^n\}$, then you can find one for your language. Here is the transition function $\delta$ (the stack initially contains the symbol \$and$q_5$is the accepting state):$\delta(q_1,\epsilon,\epsilon)=(q_5,\epsilon)\delta(q1,a,Z)=(q_1,aZ)\delta(q_1,b,aZ)=(q_2,Z)\delta(q_2,b,aZ)=(q_3,Z)\delta(q_3,b,aZ)=(q_4,Z)\delta(q_4,b,aZ)=(q_2,Z)\delta(q_4,\epsilon,\$)=(q_5,\epsilon)$