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 '16 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 '16 at 12:22

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

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

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.