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$
3
  • 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, 2013 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, 2013 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, 2013 at 22:21

2 Answers 2

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$
3
  • $\begingroup$ Nice solution. the label on the edge from the top state to the bottom one should be "a/a/bbb", no? $\endgroup$
    – mrk
    Mar 10, 2013 at 19:56
  • $\begingroup$ No. There are no a's on the stack. $\endgroup$ Mar 10, 2013 at 20:17
  • $\begingroup$ Oh yeah. Sorry. $\endgroup$
    – mrk
    Mar 10, 2013 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$
0

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.