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
    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?2011-08-23
  • 0
    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.2011-08-23
  • 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!