2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I don't understand what you want here. The statement you give is wrong. What do you want with a software? $\endgroup$ – Raphael Mar 10 '13 at 15:07
  • $\begingroup$ @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 $\endgroup$ – Anish B Mar 10 '13 at 15:08
  • $\begingroup$ 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. $\endgroup$ – Raphael Mar 10 '13 at 22:21
7
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ Nice solution. the label on the edge from the top state to the bottom one should be "a/a/bbb", no? $\endgroup$ – saadtaame Mar 10 '13 at 19:56
  • $\begingroup$ No. There are no a's on the stack. $\endgroup$ – Dave Clarke Mar 10 '13 at 20:17
  • $\begingroup$ Oh yeah. Sorry. $\endgroup$ – saadtaame Mar 10 '13 at 20:18
0
$\begingroup$

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

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