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

automatacomputer science

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

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?).

Related Question