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:
- $x$ is on top, pop $x$ out of stack
- $\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:
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)
Best Answer
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?).