Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

Problem Detail: 

I'm trying to understand the approach to constructing a PDA which accepts the language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

Asked By : Iancovici

Answered By : Patrick87

Your language is equivalent to the language $a^ib^ib^{2k}c^k$, and since concatenation is associative, this is equivalent to $(a^ib^i)(b^{2k}c^k)$.

A PDA for the first of these parts pushes an $a$ for each $a$ it sees and pops an $a$ when it sees a $b$. If the topmost stack symbol after this is $Z_0$, transition to the second PDA, which pushes a $b$ for every two $b$s it sees and then pops a $b$ for every $c$ it sees, accepting if, after this, you end up with no input and $Z_0$ as the topmost symbol.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10319