enter image description here

say you want to make a Pushdown Automaton to recognize this language.

What exactly does the +1 mean? I see in the example it just pushes an a to the stack before arriving at an acceptance state but I don't quite get why.

  • 2
    $\begingroup$ What +1 are you referring to? The only +1 I see is in the definition of the language on the top of the image. In that, it means the same as $3j+1$ means anywhere else in mathematics. The "+1" in the definition of the language doesn't "push" anything. I can't tell what your question is. Are you familiar and comfortable with set notation? If not, maybe you should ask about that on Mathematics.SE. $\endgroup$
    – D.W.
    Nov 26, 2016 at 23:37
  • $\begingroup$ Hey, yes thats what I was talking about. I don't get what am I supposed to do with the +1 $\endgroup$
    – crystyxn
    Nov 27, 2016 at 12:22

1 Answer 1


The language defined as $\{a^ib^j\mid 2i=3j+1\}$ is just the set of all strings of $i$ copies of $a$ followed by $j$ copies of $b$, where $2i=3j+1$. Trying various values of $i$ and $j$ and realizing that both $i$ and $j$ must be integers, we see that the admissible solutions are $$ (i,j)=(2, 1), (5, 3), (8, 5), (11, 7), \dotsc $$ For example, with $i=5, j=3$ we see that $2i=2(5) =10=3(3)+1=3j+1$. The corresponding strings are $$ aab,\quad a^5b^3,\quad a^8b^5,\quad a^{11}b^7 \dotsc $$ and so on.

With a bit of thought, we can make a PDA for this language by pushing two $a$ markers on the stack for each $a$ we read and then popping off three $a$s for each $b$ we see. If we wind up with a single $a$ on the stack after having read all the $b$s, we pop that off and go to the accept state.

It's worth noting that the PDA you picture does not accept the language described. That one accepts the language $\{a^nb^{2n-1}\mid n>0\}$.

  • $\begingroup$ Thanks for your answer! Can you help me correct the PDA? I thought it was correct. $\endgroup$
    – crystyxn
    Nov 29, 2016 at 7:58
  • $\begingroup$ wait I didn't mean to write a, ε -> aa but -> a, was that the mistake? $\endgroup$
    – crystyxn
    Nov 29, 2016 at 8:32

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.