Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Problem Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$

My initial idea was,

  • If we read an $a$ push a $x$ onto stack
  • If we read a $b$, there are two cases:
    1. $x$ is on top, pop $x$ out of stack
    2. $\lambda$ is on top, push $y$ onto stack.
  • Transfer to next stage, if we read a $c$, pop $y$ out of stack.

And here is my PDA: enter image description here
If the language is $L = a^nb^mc^{n + m}$, it would be easier. The tricky part is, however, the total number of $b$ is in the middle, so I wonder if my stack operation for the middle part looks reasonable? Any idea or suggestion would be greatly appreciated. Thank you.

Update (Similar PDA with different notations) enter image description here

share|cite|improve this question
up vote 2 down vote accepted

I am used to a different notation, but I believe that your PDA is almost correct. Your initial idea is correct, albeit a little unclear ($\lambda$ on top of the stack has no meaning; it is always on top of the stack). Hint: look more closely at the description of the language to see that $q_0$ should not be accepting (why?).

share|cite|improve this answer
Sorry for being careless, $q_0$ was an accepting state by accident ^_^! I was lazy when copying latex source from previous problem. Thanks for pointing that out. As for $\lambda$, I think it would better to use the stack symbol to mean the bottom of the stack. See my update for another PDA using different notation. How does it look now? – Chan Aug 23 '11 at 1:02
It looks fine. Note that both transitions from $q_0$ to $q_1$ can be accomplished by $\lambda, \lambda \to \lambda$, and depending on the definition of accepting state being used, $q_3$ may not be necessary. To clarify that last point, some definitions state that you accept if and only if you are in an accepting state and the stack is empty, while others accept any time you are in an accepting state. From your machines it seems you are operating under the latter. – Brandon Carter Aug 23 '11 at 1:29
Good point! Just read the book over again, it indeed mentioned it's only in accepting state if the stack is empty. Thanks again. – Chan Aug 23 '11 at 2:02

This language is actually the concatenation of two languages $L_1={{a^n b^n n≥0}$ and $L_2={{b^n c^n n≥1}$ (i.e. L=$L_1.L_2$)

in this way you can find the PDA more easily!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.