2
$\begingroup$

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

2 Answers 2

2

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

  • 0
    Good point! Just read the book over again, it indeed mentioned it's only in accepting state if the stack is empty. Thanks again.2011-08-23
1

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!